Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths (Q2968519)

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths

scientific article; zbMATH DE number 6695756

Language	Label	Description	Also known as
default for all languages	No label defined
English	Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths	scientific article; zbMATH DE number 6695756

Statements

instance of

scholarly article

0 references

title

Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths (English)

0 references

0 references

0 references

SIAM Journal on Discrete Mathematics

0 references

publication date

16 March 2017

0 references

full work available at URL

https://arxiv.org/abs/1703.07964

0 references

zbMATH Keywords

planar graph

0 references

minimum cut

0 references

shortest cycle

0 references

girth

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

An $O(n\log n)$ algorithm for maximum $st$-flow in a directed planar graph

0 references

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

0 references

Min $st$-cut oracle for planar graphs with near-linear preprocessing time

0 references

A linear time algorithm for the arc disjoint Menger problem in planar directed graphs

0 references

Finding shortest contractible and shortest separating cycles in embedded graphs

0 references

Multiple-source shortest paths in embedded graphs

0 references

Finding shortest non-trivial cycles in directed graphs on surfaces

0 references

Q5501344

0 references

Introduction to algorithms.

0 references

Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings

0 references

A faster algorithm for computing the girth of planar and bounded genus graphs

0 references

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

0 references

Q5417668

0 references

Global minimum cuts in surface embedded graphs

0 references

Optimally cutting a surface into a disk

0 references

Q5365107

0 references

Shortest non-crossing walks in the plane

0 references

Computing the shortest essential cycle

0 references

Planar graphs, negative weight edges, shortest paths, and near linear time

0 references

Shortest non-trivial cycles in directed and undirected surface graphs

0 references

Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

0 references

A matroid approach to finding edge connectivity and packing arborescences

0 references

Faster Scaling Algorithms for Network Problems

0 references

Submatrix maximum queries in Monge matrices are equivalent to predecessor search

0 references

Scaling Algorithms for the Shortest Paths Problem

0 references

Multi-Terminal Network Flows

0 references

Planar separators and parallel polygon triangulation.

0 references

A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

0 references

Faster shortest-path algorithms for planar graphs

0 references

Finding a Minimum Circuit in a Graph

0 references

Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs

0 references

Q4008192

0 references

Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications

0 references

Minimum $s-t$ cut in undirected planar graphs when the source and the sink are close

0 references

Minimum cuts in near-linear time

0 references

Deterministic global minimum cut of a simple graph in near-linear time

0 references

Q3138288

0 references

Multiple-source shortest paths in planar graphs

0 references

Structured recursive separator decompositions for planar graphs in linear time

0 references

Shortest paths in directed planar graphs with negative lengths: a linear-space $O(n\log^{2} n)$-time algorithm

0 references

Min-cuts and shortest cycles in planar graphs in $O(n \log\log n)$ time

0 references

Efficient approximation algorithms for shortest cycles in undirected graphs

0 references

A Separator Theorem for Planar Graphs

0 references

The complexity of determining a shortest cycle of even length

0 references

Q4856179

0 references

Q4607913

0 references

Shortest paths in planar graphs with real lengths in $O(n \log^{2} n/ \log \log n)$ time

0 references

Matching is as easy as matrix inversion

0 references

Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

0 references

Max flows in $O(nm)$ time, or better

0 references

k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON

0 references

Thick non-crossing paths and minimum-cost flows in polygonal domains

0 references

Minimum<i>s</i>-<i>t</i>Cut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time

0 references

Approximating the girth

0 references

Q5743440

0 references

A simple min-cut algorithm

0 references

Multiplying matrices faster than coppersmith-winograd

0 references

Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time

0 references

Computing the girth of a planar graph in $O(n \log n)$ time

0 references

Computing the dilation of edge-augmented graphs in metric spaces

0 references

A shortest cycle for each vertex of a graph

0 references

Finding Even Cycles Even Faster

0 references

Identifiers

zbMATH Open document ID

1358.05151

0 references

DOI

10.1137/16M1057152

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths