Edge-disjoint paths in Planar graphs with constant congestion

DOI10.1145/1132516.1132621zbMath1301.68268OpenAlexW2104935810MaRDI QIDQ2931436

Sanjeev Khanna, Chandra Chekuri, F. Bruce Shepherd

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.966.6469

zbMATH Keywords

planar graphsmulticommodity flowedge-disjoint paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Related Items

A note on multiflows and treewidth ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ The disjoint paths problem in quadratic time ⋮ The fractional congestion bound for efficient edge disjoint routing ⋮ Finding multiple induced disjoint paths in general graphs ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Disjoint paths in sparse graphs ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs