Suboptimal cuts: Their enumeration, weight and number
From MaRDI portal
Publication:5204331
DOI10.1007/3-540-55719-9_88zbMath1427.68254MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
05C30: Enumeration in graph theory
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
The Complexity of Boolean Surjective General-Valued CSPs, Must the communication graph of MPC protocols be an expander?, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, Most balanced minimum cuts, Beating the 2-approximation factor for global bicut, Improving on best-of-many-Christofides for \(T\)-tours, Efficient Algorithms for the k Smallest Cuts Enumeration
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item