Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths (Q2968519): Difference between revisions

@@ Property / arXiv ID @@
+.07964
@@ Property / arXiv ID: 1703.07964 / rank @@
+Normal rank
@@ Property / cites work @@
+An             <i>O</i>             (             <i>n</i>             log             <i>n</i>             ) algorithm for maximum             <i>st</i>             -flow in a directed planar graph
+Normal rank
@@ Property / cites work @@
+Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
+Normal rank
@@ Property / cites work @@
+Min             <i>st</i>             -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
+Normal rank
@@ Property / cites work @@
+A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
+Normal rank
@@ Property / cites work @@
+Finding shortest contractible and shortest separating cycles in embedded graphs
+Normal rank
@@ Property / cites work @@
+Multiple-Source Shortest Paths in Embedded Graphs
@@ Property / cites work: Multiple-Source Shortest Paths in Embedded Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Finding shortest non-trivial cycles in directed graphs on surfaces
+Normal rank
@@ Property / cites work @@
+Q5501344
@@ Property / cites work: Q5501344 / rank @@
+Normal rank
@@ Property / cites work @@
+Computing the Girth of a Planar Graph in Linear Time
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic Applications of Baur-Strassen’s Theorem
+Normal rank
@@ Property / cites work @@
+A faster algorithm for computing the girth of planar and bounded genus graphs
+Normal rank
@@ Property / cites work @@
+Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
+Normal rank
@@ Property / cites work @@
+Q5417668
@@ Property / cites work: Q5417668 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743478
@@ Property / cites work: Q5743478 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimally cutting a surface into a disk
@@ Property / cites work: Optimally cutting a surface into a disk / rank @@
+Normal rank
@@ Property / cites work @@
+Q5365107
@@ Property / cites work: Q5365107 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5365044
@@ Property / cites work: Q5365044 / rank @@
+Normal rank
@@ Property / cites work @@
+Computing the shortest essential cycle
@@ Property / cites work: Computing the shortest essential cycle / rank @@
+Normal rank
@@ Property / cites work @@
+Planar graphs, negative weight edges, shortest paths, and near linear time
+Normal rank
@@ Property / cites work @@
+Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
+Normal rank
@@ Property / cites work @@
+Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
+Normal rank
@@ Property / cites work @@
+A matroid approach to finding edge connectivity and packing arborescences
+Normal rank
@@ Property / cites work @@
+Faster Scaling Algorithms for Network Problems
@@ Property / cites work: Faster Scaling Algorithms for Network Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
+Normal rank
@@ Property / cites work @@
+Scaling Algorithms for the Shortest Paths Problem
@@ Property / cites work: Scaling Algorithms for the Shortest Paths Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Multi-Terminal Network Flows
@@ Property / cites work: Multi-Terminal Network Flows / rank @@
+Normal rank
@@ Property / cites work @@
+Planar separators and parallel polygon triangulation.
+Normal rank
@@ Property / cites work @@
+A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
+Normal rank
@@ Property / cites work @@
+Faster shortest-path algorithms for planar graphs
@@ Property / cites work: Faster shortest-path algorithms for planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Finding a Minimum Circuit in a Graph
@@ Property / cites work: Finding a Minimum Circuit in a Graph / rank @@
+Normal rank
@@ Property / cites work @@
+Improved algorithms for min cut and max flow in undirected planar graphs
+Normal rank
@@ Property / cites work @@
+Q4008192
@@ Property / cites work: Q4008192 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743404
@@ Property / cites work: Q5743404 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3113677
@@ Property / cites work: Q3113677 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimum cuts in near-linear time
@@ Property / cites work: Minimum cuts in near-linear time / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
+Normal rank
@@ Property / cites work @@
+Q3138288
@@ Property / cites work: Q3138288 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2921664
@@ Property / cites work: Q2921664 / rank @@
+Normal rank
@@ Property / cites work @@
+Structured recursive separator decompositions for planar graphs in linear time
+Normal rank
@@ Property / cites work @@
+Shortest paths in directed planar graphs with negative lengths
+Normal rank
@@ Property / cites work @@
+Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
+Normal rank
@@ Property / cites work @@
+Efficient approximation algorithms for shortest cycles in undirected graphs
+Normal rank
@@ Property / cites work @@
+A Separator Theorem for Planar Graphs
@@ Property / cites work: A Separator Theorem for Planar Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of determining a shortest cycle of even length
+Normal rank
@@ Property / cites work @@
+Q4856179
@@ Property / cites work: Q4856179 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4607913
@@ Property / cites work: Q4607913 / rank @@
+Normal rank
@@ Property / cites work @@
+Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
+Normal rank
@@ Property / cites work @@
+Max flows in O(nm) time, or better
@@ Property / cites work: Max flows in O(nm) time, or better / rank @@
+Normal rank
@@ Property / cites work @@
+k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
+Normal rank
@@ Property / cites work @@
+Thick non-crossing paths and minimum-cost flows in polygonal domains
+Normal rank
@@ Property / cites work @@
+Minimum<i>s</i>-<i>t</i>Cut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
+Normal rank
@@ Property / cites work @@
+Approximating the Girth
@@ Property / cites work: Approximating the Girth / rank @@
+Normal rank
@@ Property / cites work @@
+Q5743440
@@ Property / cites work: Q5743440 / rank @@
+Normal rank
@@ Property / cites work @@
+A simple min-cut algorithm
@@ Property / cites work: A simple min-cut algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+Multiplying matrices faster than coppersmith-winograd
+Normal rank
@@ Property / cites work @@
+Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
+Normal rank
@@ Property / cites work @@
+Computing the Girth of a Planar Graph in $O(n \logn)$ Time
+Normal rank
@@ Property / cites work @@
+Computing the dilation of edge-augmented graphs in metric spaces
+Normal rank
@@ Property / cites work @@
+A shortest cycle for each vertex of a graph
@@ Property / cites work: A shortest cycle for each vertex of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Finding Even Cycles Even Faster
@@ Property / cites work: Finding Even Cycles Even Faster / rank @@
+Normal rank