Generating cut conjunctions in graphs and related problems

DOI10.1007/S00453-007-9111-9zbMATH Open1147.68060DBLPjournals/algorithmica/KhachiyanBBEGM08OpenAlexW2103746934WikidataQ59560592 ScholiaQ59560592MaRDI QIDQ930604FDOQ930604

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)

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

zbMATH Keywords

GraphMatroidCut generationCut conjunctionMulticut

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• 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
• 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

(13)

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

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)