A simple linear algorithm for the edge-disjoint (s, t)-paths problem in undirected planar graphs

DOI10.1016/S0020-0190(97)00153-1zbMATH Open1336.05129MaRDI QIDQ287243FDOQ287243

Authors: Laurent Coupry 

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Recommendations

• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• The Vertex-Disjoint Menger Problem in Planar Graphs
• scientific article; zbMATH DE number 437535

zbMATH Keywords

edge-disjoint pathsflowplanar graphscombinatorial problemsclockwise circuitcounterclockwise circuitresidual graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Maximal Flow Through a Network
• Efficient Planarity Testing
• A linear-time algorithm for a special case of disjoint set union
• Title not available (Why is that?)
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• The Lattice Structure of Flow in Planar Graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

Cited In (2)

• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• 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: A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287243)