Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies

DOI10.1007/s10255-004-0196-5zbMath1104.90043OpenAlexW2035188427MaRDI QIDQ705041

Zhang, Jianzhong, Xiao-guang Yang

Publication date: 25 January 2005

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-004-0196-5

zbMATH Keywords

NP-hardedge-based upgradeeven-odd partitionnode-based upgrade

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Modifying edges of a network to obtain short subgraphs
• Approximation algorithms for certain network improvement problems
• Improving spanning trees by upgrading nodes
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Network upgrading problems
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• Upgrading bottleneck constrained forests

This page was built for publication: Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies