Hardness of the Undirected Congestion Minimization Problem

DOI10.1137/050636899zbMath1135.68433OpenAlexW1964520854MaRDI QIDQ5454245

Lisa Zhang, Matthew T. Andrews

Publication date: 28 March 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050636899

zbMATH Keywords

hardness of approximationundirected graphscongestion minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Medial Axis Based Routing Has Constant Load Balancing Factor ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Flows with unit path capacities and related packing and covering problems

This page was built for publication: Hardness of the Undirected Congestion Minimization Problem