Ancestor tree for arbitrary multi-terminal cut functions

DOI10.1007/BF02115755MaRDI QIDQ1179737zbMATH OpenOpenAlexFDO

Authors S. Singh, Chao-kun Cheng, T.-C. Hu

Publication date 27 June 1992

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02115755

zbMATH Keywords

cuts of a networkmax-flow min-cut theorem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• Very Simple Methods for All Pairs Network Flow Analysis
• Compact representations of cuts
• Efficient algorithms for generalized cut‐trees

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3797174 (Why is no real title available?)
• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• Maximal Flow Through a Network
• Multi-Terminal Network Flows
• Solution Bases of Multiterminal Cut Problems
• The maximum concurrent flow problem
• Very Simple Methods for All Pairs Network Flow Analysis

Cited in

(14)

• Exact solution of multicommodity network optimization problems with general step cost functions
• Dynamic programming and graph optimization problems
• Reconstructing edge-disjoint paths faster
• A branch-and-cut algorithm for the strong minimum energy topology in wireless sensor networks
• The multi-layered network design problem
• An algorithm for computing maximum solution bases
• A note on minimizing submodular functions
• Tight Bounds for Gomory-Hu-like Cut Counting
• Space complexity of vertex connectivity oracles
• Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
• The structure of minimum vertex cuts
• Optimal sensitivity oracle for Steiner mincut
• Minimum+1 Steiner cut and dual edge sensitivity oracle: bridging gap between global and (s,t)-cut
• Flow trees for vertex-capacitated networks

This page was built for publication: Ancestor tree for arbitrary multi-terminal cut functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179737)