A linear-time algorithm for edge-disjoint paths in planar graphs
DOI10.1007/BF01294465zbMATH Open0841.05086OpenAlexW2066881276MaRDI QIDQ1842575FDOQ1842575
Authors: 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
Recommendations
edge-disjoint pathsplanar graphslinear-time algorithmevenness conditiontheorem of Okamura and Seymour
Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)
Cites Work
- A class of algorithms which require nonlinear time to maintain disjoint sets
- A linear-time algorithm for a special case of disjoint set union
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Algorithms for routing in planar graphs
- Faster shortest-path algorithms for planar graphs
- Title not available (Why is that?)
- Maximum Flow in Planar Networks
- Multicommodity flows in planar graphs
- An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
- Routing through a generalized switchbox
- On multicommodity flows in planar graphs
- Algorithms and computation. 4th international symposium, ISAAC '93, Hong Kong, December 15--17, 1993. Proceedings
- Title not available (Why is that?)
Cited In (33)
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- Title not available (Why is that?)
- Euclidean maximum matchings in the plane -- local to global
- Title not available (Why is that?)
- 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
- The order-interval hypergraph of a finite poset and the König property
- Improved approximation for node-disjoint paths in planar graphs
- Title not available (Why is that?)
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Title not available (Why is that?)
- Edge-disjoint routing in plane switch graphs in linear time.
- LINEAR-TIME ALGORITHMS FOR DISJOINT TWO-FACE PATHS PROBLEMS IN PLANAR GRAPHS
- Title not available (Why is that?)
- A near-linear-time algorithm for computing replacement paths in planar directed graphs
- Online interval scheduling with predictions
- On complexity, representation and approximation of integral multicommodity flows
- Title not available (Why is that?)
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- An exponential time parameterized algorithm for planar disjoint paths
- Title not available (Why is that?)
- A linear time algorithm for finding three edge-disjoint paths in Eulerian networks
- Edge-disjoint paths in a grid bounded by two nested rectangles
- Euclidean maximum matchings in the plane -- local to global
- Finding an Even Simple Path in a Directed Planar Graph
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works
- Edge-disjoint paths in planar graphs
- A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes
- An algorithm for node-capacitated ring routing
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- A linear programming formulation of Mader's edge-disjoint paths problem
- Maximum Edge-Disjoint Paths Problem in Planar Graphs
This page was built for publication: A linear-time algorithm for edge-disjoint paths in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1842575)
