Suboptimal cuts: Their enumeration, weight and number
From MaRDI portal
Publication:5204331
DOI10.1007/3-540-55719-9_88zbMath1427.68254OpenAlexW1542177083MaRDI QIDQ5204331
Vijay V. Vazirani, Mihalis Yannakakis
Publication date: 4 December 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55719-9_88
Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Improving on best-of-many-Christofides for \(T\)-tours ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ On the minimum \(s-t\) cut problem with budget constraints ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Must the communication graph of MPC protocols be an expander? ⋮ Most balanced minimum cuts ⋮ Beating the 2-approximation factor for global bicut
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- On the structure of all minimum cuts in a network and applications
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
This page was built for publication: Suboptimal cuts: Their enumeration, weight and number
