Enumerating parametric global minimum cuts by random interleaving

DOI10.1145/2897518.2897578MaRDI QIDQ5361860zbMATH OpenOpenAlexFDO

Authors David R. Karger

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2897518.2897578

zbMATH Keywords

graph algorithmsminimum cuts

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Sensitivity, stability, parametric optimization (90C31) Programming involving graphs or networks (90C35)

Recommendations

• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
• Faster algorithms for next breakpoint and max value for parametric global minimum cuts
• Structural and algorithmic properties for parametric minimum cuts
• Minimum cuts in parametric networks

Cited in

(9)

• Combinatorial optimization with interaction costs: complexity and solvable cases
• An approximation algorithm for a general class of multi-parametric optimization problems
• Complexity of source-sink monotone 2-parameter min cut
• Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
• Faster algorithms for next breakpoint and max value for parametric global minimum cuts
• Maximum flows in parametric graph templates
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
• A survey of exact and approximation algorithms for linear-parametric optimization problems
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs

This page was built for publication: Enumerating parametric global minimum cuts by random interleaving

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