An O( n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs

DOI10.1145/2438645.2438648MaRDI QIDQ2933646zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithmedge-disjoint pathsEulerian graph4-edge-connected graph

Mathematics Subject Classification ID

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)

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

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
• Almost polynomial hardness of node-disjoint paths in grids
• 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)