Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

DOI10.1145/301250.301262zbMath1346.68102OpenAlexW2079300367MaRDI QIDQ5890864

Mihalis Yannakakis, Rajmohan Rajaraman, Sanjeev Khanna, Bruce Shepherd, Venkatesan Guruswami

Publication date: 29 September 2016

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

Full work available at URL: https://repository.upenn.edu/cis_papers/109

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Call control with \(k\) rejections ⋮ Paths and trails in edge-colored graphs ⋮ A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ Connectivity and inference problems for temporal networks ⋮ On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints ⋮ Balanced paths in acyclic networks: Tractable cases and related approaches ⋮ Path problems in generalized stars, complete graphs, and brick wall graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Short length Menger's theorem and reliable optical routing ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ Paths and Trails in Edge-Colored Graphs ⋮ On three approaches to length-bounded maximum multicommodity flow with unit edge-lengths ⋮ A note on the greedy algorithm for the unsplittable flow problem ⋮ Flows on few paths: Algorithms and lower bounds ⋮ Flows with Unit Path Capacities and Related Packing and Covering Problems