A linear-time algorithm for edge-disjoint paths in planar graphs

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 (29)

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
Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
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?)
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
An exponential time parameterized algorithm for planar disjoint paths
Title not available (Why is that?)
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

   Recommendations

Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time 👍 👎
Edge-disjoint paths in planar graphs 👍 👎
A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs 👍 👎
Title not available (Why is that?) 👍 👎

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)