Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations
Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations
复制标题
重温参数化多终端问题：最大流、最小割和割树计算
DOI：
10.1016/j.disopt.2006.05.003
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Afonso Ferreira
中科院分区：
文献类型：
--
作者：
D. Barth;P. Berthomé;Madiagne Diallo;Afonso Ferreira
给定一个无向网络，多终端网络流分析在于确定所有对的最大流量值。本文考虑了一个允许某些边容量变化的无向网络，并分析了这种变化对所有对最大流量值的影响。我们首先给出了单参数容量情况下的一个有效算法，然后提出了多参数容量情况下的推广。此外，我们还研究了Gomory-Hu割树关系。
Given an undirected network, the multi-terminal network flows analysis consists in determining the all pairs maximum flow values. In this paper, we consider an undirected network in which some edge capacities are allowed to vary and we analyze the impact of such variations on the all pairs maximum flow values. We first provide an efficient algorithm for the single parametric capacity case, and then propose a generalization to the case of multiple parametric capacities. Moreover, we provide a study on Gomory–Hu cut-tree relationships.