A linear-time algorithm for edge-disjoint paths in planar graphs
From MaRDI portal
Publication:1842575
DOI10.1007/BF01294465zbMath0841.05086OpenAlexW2066881276MaRDI QIDQ1842575
Dorothea Wagner, Karsten Weihe
Publication date: 14 July 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01294465
planar graphsedge-disjoint pathslinear-time algorithmevenness conditiontheorem of Okamura and Seymour
Paths and cycles (05C38) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (13)
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Euclidean maximum matchings in the plane -- local to global ⋮ The order-interval hypergraph of a finite poset and the König property ⋮ A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes ⋮ Online interval scheduling with predictions ⋮ Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ On complexity, representation and approximation of integral multicommodity flows ⋮ An algorithm for node-capacitated ring routing ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time
Cites Work
- Unnamed Item
- Unnamed Item
- A class of algorithms which require nonlinear time to maintain disjoint sets
- A linear-time algorithm for a special case of disjoint set union
- Algorithms for routing in planar graphs
- Multicommodity flows in planar graphs
- Algorithms and computation. 4th international symposium, ISAAC '93, Hong Kong, December 15--17, 1993. Proceedings
- On multicommodity flows in planar graphs
- An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
- Routing through a generalized switchbox
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Maximum Flow in Planar Networks
- Faster shortest-path algorithms for planar graphs
This page was built for publication: A linear-time algorithm for edge-disjoint paths in planar graphs