Logarithmic hardness of the undirected edge-disjoint paths problem

DOI10.1145/1183907.1183910zbMath1326.68143OpenAlexW2058091369MaRDI QIDQ3455215

Lisa Zhang, Matthew T. Andrews

Publication date: 4 December 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1183907.1183910

zbMATH Keywords

hardness of approximationedge-disjoint pathsundirected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Inapproximability of $H$-Transversal/Packing ⋮ Unnamed Item ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Unnamed Item

This page was built for publication: Logarithmic hardness of the undirected edge-disjoint paths problem