Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time

DOI10.1016/J.TCS.2011.05.017zbMATHOpenAlexMaRDI QIDQ764322FDO

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

zbMATH Keywords

maximum flowcounting and samplingmaximal antichains in partially ordered setsminimum \((s,t)\)-cutsweighted planar graphs

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 60387 (Why is no real title available?)
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• A new approach to the maximum-flow problem
• An \(O(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph
• Calculating bounds on reachability and connectedness in stochastic networks
• Combinatorial aspects of network reliability
• Computing Network Reliability in Time Polynomial in the Number of Cuts
• Counting almost minimum cutsets with reliability applications
• Counting the number of minimum cuts in undirected multigraphs
• Efficient Planarity Testing
• Introduction to algorithms
• Maximal Flow Through a Network
• Maximum Flow in Planar Networks
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

Cited in

(11)

• Counting and sampling minimum cuts in genus \(g\) graphs
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• An efficient oracle for counting shortest paths in planar graphs
• An efficient oracle for counting shortest paths in planar graphs
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• Minimum planar multi-sink cuts with connectivity priors
• Counting and sampling minimum cuts in genus g graphs
• Integrating and sampling cuts in bounded treewidth graphs
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Contiguous minimum single-source-multi-sink cuts in weighted planar graphs
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time

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)