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

DOI10.1007/3-540-55719-9_88zbMATH Open1427.68254OpenAlexW1542177083MaRDI QIDQ5204331FDOQ5204331

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph

Cited In (16)

• Most balanced minimum cuts
• Counting almost minimum cutsets with reliability applications
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)
• Title not available (Why is that?)
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• The Complexity of Boolean Surjective General-Valued CSPs
• Efficient Algorithms for the k Smallest Cuts Enumeration
• Title not available (Why is that?)
• Title not available (Why is that?)
• Beating the 2-approximation factor for global bicut
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Must the communication graph of MPC protocols be an expander?
• Improving on best-of-many-Christofides for \(T\)-tours
• On the minimum \(s-t\) cut problem with budget constraints
• Title not available (Why is that?)

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)