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

0.00 Avg rating0 Votes
Article ID: iaor2007917
Country: Netherlands
Volume: 3
Issue: 3
Start Page Number: 195
End Page Number: 205
Publication Date: Sep 2006
Journal: Discrete Optimization
Authors: , , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.