Hardness of the Undirected Congestion Minimization Problem

DOI10.1137/050636899MaRDI QIDQ5454245zbMATH OpenOpenAlexFDO

Authors Lisa Zhang, Matthew 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

congestion minimizationhardness of approximationundirected graphs

Mathematics Subject Classification ID

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

Recommendations

• Hardness of the undirected congestion minimization problem
• Logarithmic hardness of the directed congestion minimization problem
• Almost-tight hardness of directed congestion minimization
• Logarithmic hardness of the undirected edge-disjoint paths problem
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

Cited in

(12)

• Flows with unit path capacities and related packing and covering problems
• Routing in undirected graphs with constant congestion
• Logarithmic hardness of the directed congestion minimization problem
• Hardness of routing for minimizing superlinear polynomial cost in directed graphs
• Almost-tight hardness of directed congestion minimization
• Medial axis based routing has constant load balancing factor
• Hardness of the undirected congestion minimization problem
• New hardness results for congestion minimization and machine scheduling
• New hardness results for congestion minimization and machine scheduling
• Improved hardness of approximation of diameter in the CONGEST model
• Cluster before you hallucinate: node-capacitated network design and energy efficient routing
• Hardness and approximation of traffic grooming

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5454245)