On enumerating minimal dicuts and strongly connected subgraphs
From MaRDI portal
Publication:2471808
DOI10.1007/s00453-007-9074-xzbMath1203.68122OpenAlexW2021178630MaRDI QIDQ2471808
Endre Boros, Khaled M. Elbassioni, Vladimir A. Gurvich
Publication date: 18 February 2008
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-007-9074-x
Related Items
Enumerating minimal dominating sets in chordal bipartite graphs, Invited talks, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, FINDING SIMPLICES CONTAINING THE ORIGIN IN TWO AND THREE DIMENSIONS, An incremental polynomial time algorithm to enumerate all minimal edge dominating sets, Scientific contributions of Leo Khachiyan (a short overview), Lower bounds for three algorithms for transversal hypergraph generation, On the complexity of solution extension of optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Random generation of combinatorial structures from a uniform distribution
- A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
- Extracting maximal information about sets of minimum cuts
- On enumerating all minimal solutions of feedback problems
- A paradigm for listing \((s,t)\)-cuts in graphs
- Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
- Computing Network Reliability in Time Polynomial in the Number of Cuts
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Determination of All Minimal Cut-Sets between a Vertex Pair in an Undirected Graph
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Generating all vertices of a polyhedron is hard
- An efficient network flow code for finding all minimum cost \(s-t\) cutsets
