Generating cut conjunctions in graphs and related problems

DOI10.1007/s00453-007-9111-9zbMath1147.68060OpenAlexW2103746934WikidataQ59560592 ScholiaQ59560592MaRDI QIDQ930604

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

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

GraphMatroidCut generationCut conjunctionMulticut

Mathematics Subject Classification ID

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

Related Items

Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Polynomial-delay and polynomial-space enumeration of large maximal matchings ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On generating all maximal independent sets
• On enumerating all minimal solutions of feedback problems
• A note on finding the bridges of a graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• 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
• The Complexity of Multiterminal Cuts
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
• Mathematical Foundations of Computer Science 2004
• On the Complexity of Some Enumeration Problems for Matroids
• Multi-Commodity Network Flows