Generating cut conjunctions in graphs and related problems

DOI10.1007/S00453-007-9111-9MaRDI QIDQ930604zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Endre Boros, Konrad Borys, Vladimir Gurvich, Kazuhisa Makino, Leonid G. Khachiyan, Khaled Elbassioni

Publication date 1 July 2008

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-007-9111-9

zbMATH Keywords

Cut conjunctionCut generationGraphMatroidMulticut

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms and Computation
• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 1234600
• Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
• Extracting maximal information about sets of minimum cuts

Cites work

• A note on finding the bridges of a graph
• An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Mathematical Foundations of Computer Science 2004
• Multi-Commodity Network Flows
• On enumerating all minimal solutions of feedback problems
• On generating all maximal independent sets
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the Complexity of Some Enumeration Problems for Matroids
• The Complexity of Multiterminal Cuts
• Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

Cited in

(15)

• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• scientific article; zbMATH DE number 1234600 (Why is no real title available?)
• scientific article; zbMATH DE number 1757966 (Why is no real title available?)
• Reflections on generating (disjunctive) cuts
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Enumerating minimal transversals of hypergraphs without small holes
• scientific article; zbMATH DE number 7559431 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Algorithms and Computation
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
• Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond
• Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
• Enumerating minimal dominating sets in chordal bipartite graphs
• Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: Generating cut conjunctions in graphs and related problems

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