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

DOI10.1006/jagm.1996.0831zbMath0866.68074OpenAlexW2009669213MaRDI QIDQ3128989

Karsten Weihe

Publication date: 27 April 1997

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/a2b65cb0a3ba840c90ccfb997e6ca334d25b9fec

zbMATH Keywords

undirected planar graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time ⋮ Maximum flow in directed planar graphs with vertex capacities ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time

This page was built for publication: Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time