Generating cut conjunctions in graphs and related problems
DOI10.1007/S00453-007-9111-9zbMATH Open1147.68060DBLPjournals/algorithmica/KhachiyanBBEGM08OpenAlexW2103746934WikidataQ59560592 ScholiaQ59560592MaRDI QIDQ930604FDOQ930604
Konrad Borys, Leonid G. Khachiyan, Kazuhisa Makino, Endre Boros, Vladimir Gurvich, 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
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)
Cites Work
- Title not available (Why is that?)
- A note on finding the bridges of a graph
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- The Complexity of Multiterminal Cuts
- Title not available (Why is that?)
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On generating all maximal independent sets
- 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
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- EFFICIENTLY SCANNING ALL SPANNING TREES OF AN UNDIRECTED GRAPH
- Multi-Commodity Network Flows
- On enumerating all minimal solutions of feedback problems
- Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
- On the Complexity of Some Enumeration Problems for Matroids
- Mathematical Foundations of Computer Science 2004
Cited In (11)
- Mathematical Foundations of Computer Science 2004
- Title not available (Why is that?)
- Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
- Enumerating minimal dominating sets in chordal bipartite graphs
- Enumerating Minimal Transversals of Hypergraphs without Small Holes
- Reflections on generating (disjunctive) cuts
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
- Title not available (Why is that?)
- Polynomial-delay and polynomial-space enumeration of large maximal matchings
- Scientific contributions of Leo Khachiyan (a short overview)
Recommendations
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)
