An O( n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
DOI10.1145/2438645.2438648zbMATH Open1301.05333OpenAlexW2035272561MaRDI QIDQ2933646FDOQ2933646
Authors: Ken-ichi Kawarabayashi, Yusuke Kobayashi 
Publication date: 5 December 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2438645.2438648
Recommendations
- An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- scientific article; zbMATH DE number 1263178
- An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)
Cited In (9)
- Routing in undirected graphs with constant congestion
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- Approximating maximum integral multiflows on bounded genus graphs
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
- Improved approximation for node-disjoint paths in grids with sources on the boundary
- Title not available (Why is that?)
- New hardness results for routing on disjoint paths
- The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
This page was built for publication: An \(O(\log n)\)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933646)
