Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths
From MaRDI portal
Publication:2968519
DOI10.1137/16M1057152zbMath1358.05151arXiv1703.07964MaRDI QIDQ2968519
Publication date: 16 March 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1703.07964
Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)
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
- Computing the shortest essential cycle
- Planar separators and parallel polygon triangulation.
- Efficient approximation algorithms for shortest cycles in undirected graphs
- Computing the dilation of edge-augmented graphs in metric spaces
- The complexity of determining a shortest cycle of even length
- Matching is as easy as matrix inversion
- Optimally cutting a surface into a disk
- A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
- A matroid approach to finding edge connectivity and packing arborescences
- A shortest cycle for each vertex of a graph
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Multiple-Source Shortest Paths in Embedded Graphs
- Finding shortest contractible and shortest separating cycles in embedded graphs
- Shortest paths in directed planar graphs with negative lengths
- Approximating the Girth
- Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
- Algorithmic Applications of Baur-Strassen’s Theorem
- A faster algorithm for computing the girth of planar and bounded genus graphs
- Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
- 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
- Thick non-crossing paths and minimum-cost flows in polygonal domains
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Multi-Terminal Network Flows
- A Separator Theorem for Planar Graphs
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Finding a Minimum Circuit in a Graph
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- Finding Even Cycles Even Faster
- A simple min-cut algorithm
- k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
- Faster Scaling Algorithms for Network Problems
- Scaling Algorithms for the Shortest Paths Problem
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
- Computing the Girth of a Planar Graph in $O(n \logn)$ Time
- Finding shortest non-trivial cycles in directed graphs on surfaces
- Multiplying matrices faster than coppersmith-winograd
- Improved algorithms for min cut and max flow in undirected planar graphs
- Minimum cuts in near-linear time
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Structured recursive separator decompositions for planar graphs in linear time
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Max flows in O(nm) time, or better
- Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
- Computing the Girth of a Planar Graph in Linear Time
- Faster shortest-path algorithms for planar graphs
