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

DOI10.1016/S0020-0190(97)00153-1zbMath1336.05129MaRDI QIDQ287243

Laurent Coupry

Publication date: 26 May 2016

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

zbMATH Keywords

planar graphscombinatorial problemsflowedge-disjoint pathsclockwise circuitcounterclockwise circuitresidual graph

Mathematics Subject Classification ID

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

Related Items

Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• The Lattice Structure of Flow in Planar Graphs
• Maximal Flow Through a Network
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Efficient Planarity Testing