Compact representations of cuts

DOI10.1137/S0895480196312334MaRDI QIDQ2706189zbMATH OpenFDO

Authors David Hartvigsen

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480196312334

zbMATH Keywords

min-cut\(k\)-cutflow tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• Compact cactus representations of all non-trivial min-cuts
• Compacting cuts. A new linear formulation for minimum cut
• Compacting cuts, a new linear formulation for minimum cut
• scientific article; zbMATH DE number 140138
• The complexity of cutting complexes
• Maximal cuts in arbitrary dimension
• Hilbert bases of cuts
• Cutting hyperplane arrangements
• Canonical cactus representation for miminum cuts
• Algebraic cuts

Cited in

(11)

• Solution Bases of Multiterminal Cut Problems
• Flow trees for vertex-capacitated networks
• Counterexamples for Directed and Node Capacitated Cut-Trees
• Extracting maximal information about sets of minimum cuts
• When do Gomory-Hu subtrees exist?
• Exact cutting in spaces of cusp forms with characters
• Canonical cactus representation for miminum cuts
• Compacting cuts. A new linear formulation for minimum cut
• Tree packing and approximating k-cuts
• Maximum concurrent flows and minimum cuts
• Compacting cuts, a new linear formulation for minimum cut

This page was built for publication: Compact representations of cuts

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