An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs

DOI10.1145/2438645.2438648zbMath1301.05333OpenAlexW2035272561MaRDI QIDQ2933646

Yusuke Kobayashi, Ken-ichi Kawarabayashi

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 algorithmEulerian graphedge-disjoint paths4-edge-connected graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Related Items (6)

Approximating maximum integral multiflows on bounded genus graphs ⋮ Unnamed Item ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Unnamed Item

This page was built for publication: An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs