Enumerating parametric global minimum cuts by random interleaving

DOI10.1145/2897518.2897578zbMath1376.05150OpenAlexW2411775271MaRDI QIDQ5361860

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

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

Related Items (7)

Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ Complexity of source-sink monotone 2-parameter min cut ⋮ Maximum flows in parametric graph templates ⋮ Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs ⋮ Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ An approximation algorithm for a general class of multi-parametric optimization problems

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