Edge-disjoint paths in planar graphs
From MaRDI portal
Publication:1069956
DOI10.1016/0095-8956(85)90046-2zbMath0583.05036OpenAlexW2012969943MaRDI QIDQ1069956
Publication date: 1985
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(85)90046-2
Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (30)
On finding Min-Min disjoint paths ⋮ On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary ⋮ Sonet ring sizing with genetic algorithms ⋮ The shortest multipaths problem in a capacitated dense channel ⋮ An Improved Upper Bound for the Ring Loading Problem ⋮ Optimization in telecommunication networks ⋮ A Combinatorial Algorithm for the Planar Multiflow Problem with Demands Located on Three Holes ⋮ Finding \(K\) dissimilar paths: single-commodity and discretized flow formulations ⋮ Online interval scheduling with predictions ⋮ Upgrading edge-disjoint paths in a ring ⋮ A polynomial time approximation scheme for embedding hypergraph in a weighted cycle ⋮ Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ The hardness of routing two pairs on one face ⋮ On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem ⋮ An algorithm for node-capacitated ring routing ⋮ On obstructions to small face covers in planar graphs ⋮ Algorithms for routing around a rectangle ⋮ Disjoint paths in sparse graphs ⋮ Ideal clutters ⋮ A cycle augmentation algorithm for minimum cost multicommodity flows on a ring ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ A Note on the Ring Loading Problem ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Approximations for the disjoint paths problem in high-diameter planar networks ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ Algorithms for routing in planar graphs
Cites Work
This page was built for publication: Edge-disjoint paths in planar graphs
