Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs

DOI10.1007/978-3-319-55911-7_41zbMath1485.68201OpenAlexW2599632310MaRDI QIDQ2988851

Fa Zhang, Yangguang Shi, Zhi-yong Liu

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_41

zbMATH Keywords

directed graphshardness of approximationnetwork energy efficiencysuperlinear polynomial cost

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Randomized oblivious integral routing for minimizing power cost
• Online Primal-Dual for Non-linear Optimization with Applications to Speed Scaling
• Logarithmic hardness of the directed congestion minimization problem
• Minimum-Cost Network Design with (Dis)economies of Scale
• Hardness of the undirected congestion minimization problem
• Multicast Routing for Energy Minimization Using Speed Scaling

This page was built for publication: Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs