On enumerating minimal dicuts and strongly connected subgraphs

DOI10.1007/S00453-007-9074-XMaRDI QIDQ2471808zbMATH OpenOpenAlexFDO

Authors Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Publication date 18 February 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-9074-x

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Integer Programming and Combinatorial Optimization
• Mathematical Foundations of Computer Science 2004
• On the Complexity of Some Enumeration Problems for Matroids
• On enumerating all minimal solutions of feedback problems
• Algorithms and Computation

Cites work

• A paradigm for listing \((s,t)\)-cuts in graphs
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• An efficient network flow code for finding all minimum cost \(s-t\) cutsets
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Computing Network Reliability in Time Polynomial in the Number of Cuts
• Determination of All Minimal Cut-Sets between a Vertex Pair in an Undirected Graph
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Extracting maximal information about sets of minimum cuts
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Generating all vertices of a polyhedron is hard
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On enumerating all minimal solutions of feedback problems
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Random generation of combinatorial structures from a uniform distribution

Cited in

(13)

• Lower bounds for three algorithms for transversal hypergraph generation
• On the complexity of solution extension of optimization problems
• Invited talks
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Mathematical Foundations of Computer Science 2004
• Finding simplices containing the origin in two and three dimensions
• Integer Programming and Combinatorial Optimization
• Polynomial-delay generation of functional digraphs up to isomorphism
• A linear delay algorithm of enumerating strongly-connected induced subgraphs based on SSD set system
• A linear-delay algorithm for enumerating strongly-connected induced subgraphs based on SSD set system
• Enumerating the irreducible closed sets of an acyclic implicational base of bounded degree
• Enumerating minimal dominating sets in chordal bipartite graphs
• Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: On enumerating minimal dicuts and strongly connected subgraphs

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