Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
From MaRDI portal
Publication:764322
DOI10.1016/j.tcs.2011.05.017zbMath1236.05066OpenAlexW2049188514MaRDI QIDQ764322
Ivona Bezáková, Adam J. Friedlander
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.017
maximum flowcounting and samplingmaximal antichains in partially ordered setsminimum \((s,t)\)-cutsweighted planar graphs
Computing methodologies for image processing (68U10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items
On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, Counting and sampling minimum cuts in genus \(g\) graphs, Unnamed Item, An efficient oracle for counting shortest paths in planar graphs, Integrating and Sampling Cuts in Bounded Treewidth Graphs, An efficient oracle for counting shortest paths in planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Random generation of combinatorial structures from a uniform distribution
- Combinatorial aspects of network reliability
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Maximal Flow Through a Network
- Computing Network Reliability in Time Polynomial in the Number of Cuts
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Calculating bounds on reachability and connectedness in stochastic networks
- Counting almost minimum cutsets with reliability applications
- A new approach to the maximum-flow problem
- Maximum Flow in Planar Networks
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Counting the number of minimum cuts in undirected multigraphs
- Efficient Planarity Testing
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
