Suboptimal cuts: their enumeration, weight and number (extended abstract)

DOI10.1007/3-540-55719-9_88MaRDI QIDQ5204331zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Computing All Small Cuts in an Undirected Network
• scientific article; zbMATH DE number 1555934
• Efficient Algorithms for the k Smallest Cuts Enumeration
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• scientific article; zbMATH DE number 3906193

Cites work

• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• scientific article; zbMATH DE number 432788 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 177555 (Why is no real title available?)
• On the structure of all minimum cuts in a network and applications
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

Cited in

(19)

• Beating the 2-approximation factor for global bicut
• Improving on best-of-many-Christofides for \(T\)-tours
• A generalized framework for listing cuts and graphs
• scientific article; zbMATH DE number 3848942 (Why is no real title available?)
• Efficient Algorithms for the k Smallest Cuts Enumeration
• scientific article; zbMATH DE number 3906193 (Why is no real title available?)
• Counting almost minimum cutsets with reliability applications
• scientific article; zbMATH DE number 2050721 (Why is no real title available?)
• scientific article; zbMATH DE number 1555934 (Why is no real title available?)
• The Complexity of Boolean Surjective General-Valued CSPs
• Must the communication graph of MPC protocols be an expander?
• On the minimum \(s-t\) cut problem with budget constraints
• Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• Most balanced minimum cuts

This page was built for publication: Suboptimal cuts: their enumeration, weight and number (extended abstract)

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