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

DOI10.1016/S0020-0190(97)00153-1MaRDI QIDQ287243zbMATHFDO

Authors Laurent Coupry

Publication date 26 May 2016

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

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)

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

Cites work

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

Cited in

(3)

• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs (extended abstract)
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

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)