Minimum Cuts in Surface Graphs
From MaRDI portal
Publication:5885599
DOI10.1137/19M1291820OpenAlexW2980163628MaRDI QIDQ5885599
Amir Nayyeri, Jeff Erickson, Kyle Fox, Erin Wolf Chambers
Publication date: 4 April 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.04278
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) 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) Duality in applied homological algebra and category theory (aspects of algebraic topology) (55U30)
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- 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
- Graph-encoded maps
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Using generic programming for designing a data structure for polyhedral surfaces
- Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
- Easy and difficult objective functions for max cut
- Graphs on surfaces and their applications. Appendix by Don B. Zagier
- Diameter and treewidth in minor-closed graph families
- Recognizing weakly simple polygons
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Spanning trees of dual graphs
- Multiple-Source Shortest Paths in Embedded Graphs
- Optimal homologous cycles, total unimodularity, and linear programming
- Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
- Minimum cycle and homology bases of surface-embedded graphs
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
- Beyond the flow decomposition barrier
- Isomorphism testing for embeddable graphs through definability
- Maximal Flow Through a Network
- The cycle space of an embedded graph
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Optimal pants decompositions and shortest homotopic cycles on an orientable surface
- Tightening non-simple paths and cycles on surfaces
- An O (n log n) algorithm for maximum st-flow in a directed planar graph
- Shortest Cut Graph of a Surface with Prescribed Vertex Set
- 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
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A new approach to the maximum-flow problem
- Maximum Flow in Planar Networks
- Generalized Nested Dissection
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- A simple min-cut algorithm
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Local Flow Partitioning for Faster Edge Connectivity
- Deterministic Edge Connectivity in Near-Linear Time
- Planar Graphs
- Flow in Planar Graphs with Multiple Sources and Sinks
- Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
- Homology Flows, Cohomology Cuts
- Quantifying Homology Classes
- Graphs on Surfaces
- Flows in One-Crossing-Minor-Free Graphs
- Computational topology and the Unique Games Conjecture
- Holiest minimum-cost paths and flows in surface graphs
- On the History of Combinatorial Optimization (Till 1960)
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Detecting Weakly Simple Polygons
- Minimum cuts and shortest homologous cycles
- Tightening Nonsimple Paths and Cycles on Surfaces
- Shortest non-trivial cycles in directed surface graphs
- Finding shortest non-trivial cycles in directed graphs on surfaces
- Improved algorithms for min cut and max flow in undirected planar graphs
- Minimum cuts in near-linear time
- Max flows in O(nm) time, or better
- SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
- Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
- Many distances in planar graphs
- Faster shortest-path algorithms for planar graphs
This page was built for publication: Minimum Cuts in Surface Graphs
