Counting and sampling minimum cuts in genus \(g\) graphs
From MaRDI portal
Publication:471138
DOI10.1007/s00454-014-9623-4zbMath1302.05181OpenAlexW2073350357MaRDI QIDQ471138
Amir Nayyeri, Kyle Fox, Erin Wolf Chambers
Publication date: 14 November 2014
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-014-9623-4
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Splitting (complicated) surfaces is hard
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Combinatorial aspects of network reliability
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
- Diameter and treewidth in minor-closed graph families
- Orientable imbeddings of Cayley graphs
- Shortest paths in directed planar graphs with negative lengths
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Flows in One-Crossing-Minor-Free Graphs
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- Isomorphism testing for embeddable graphs through definability
- Maximal Flow Through a Network
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- A survey on Mesh Segmentation Techniques
- An O (n log n) algorithm for maximum st-flow in a directed planar graph
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks
- Calculating bounds on reachability and connectedness in stochastic networks
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Maximum Flow in Planar Networks
- Generalized Nested Dissection
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Counting the number of minimum cuts in undirected multigraphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Topology for Computing
- Homology Flows, Cohomology Cuts
- Minimum cuts and shortest homologous cycles
- Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
- Improved algorithms for min cut and max flow in undirected planar graphs
- Max flows in O(nm) time, or better
- Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
- Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
- Faster shortest-path algorithms for planar graphs
