Hardness of the undirected edge-disjoint paths problem
From MaRDI portal
Publication:3581428
DOI10.1145/1060590.1060632zbMath1192.68309OpenAlexW1989234747MaRDI QIDQ3581428
Lisa Zhang, Matthew T. Andrews
Publication date: 16 August 2010
Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1060590.1060632
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
The maximum integer multiterminal flow problem in directed graphs, Finding disjoint paths with related path costs, The complexity of minimum convex coloring, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Approximability of Packing Disjoint Cycles, The maximum edge-disjoint paths problem in complete graphs, Approximability of packing disjoint cycles, Routing in Undirected Graphs with Constant Congestion, New Hardness Results for Routing on Disjoint Paths
