Almost-tight hardness of directed congestion minimization
DOI10.1145/1455248.1455251zbMATH Open1325.68094OpenAlexW1978807904MaRDI QIDQ3452193FDOQ3452193
Authors: Lisa Zhang, Matthew Andrews 
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1455248.1455251
Recommendations
- Logarithmic hardness of the directed congestion minimization problem
- Hardness of the undirected congestion minimization problem
- 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
Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (9)
- Routing in undirected graphs with constant congestion
- Hardness of the Undirected Congestion Minimization Problem
- New hardness results for congestion minimization and machine scheduling
- Logarithmic hardness of the directed congestion minimization problem
- New hardness results for congestion minimization and machine scheduling
- Hardness of the undirected congestion minimization problem
- Hardness of routing for minimizing superlinear polynomial cost in directed graphs
- Title not available (Why is that?)
- Improved hardness of approximation of diameter in the CONGEST model
This page was built for publication: Almost-tight hardness of directed congestion minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452193)
