Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
DOI10.1016/J.TCS.2011.05.017zbMATH Open1236.05066OpenAlexW2049188514MaRDI QIDQ764322FDOQ764322
Authors: 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
Recommendations
- Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
- Contiguous minimum single-source-multi-sink cuts in weighted planar graphs
- Minimum planar multi-sink cuts with connectivity priors
- Minimum \(s-t\) cut in undirected planar graphs when the source and the sink are close
- scientific article; zbMATH DE number 6469225
maximum flowcounting and samplingmaximal antichains in partially ordered setsminimum \((s,t)\)-cutsweighted planar graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for image processing (68U10) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)
Cites Work
- Maximal Flow Through a Network
- Introduction to algorithms
- Random generation of combinatorial structures from a uniform distribution
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Efficient Planarity Testing
- A new approach to the maximum-flow problem
- Calculating bounds on reachability and connectedness in stochastic networks
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- Combinatorial aspects of network reliability
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- 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
- Counting almost minimum cutsets with reliability applications
- Computing Network Reliability in Time Polynomial in the Number of Cuts
- Title not available (Why is that?)
Cited In (10)
- Title not available (Why is that?)
- Counting and sampling minimum cuts in genus g graphs
- On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
- An efficient oracle for counting shortest paths in planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- Counting and sampling minimum cuts in genus \(g\) graphs
- Integrating and Sampling Cuts in Bounded Treewidth Graphs
- Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
- A fast algorithm for minimum weight odd circuits and cuts in planar graphs
- Contiguous minimum single-source-multi-sink cuts in weighted planar graphs
This page was built for publication: Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764322)
