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

DOI10.1007/S10255-004-0196-5MaRDI QIDQ705041zbMATH OpenOpenAlexFDO

Authors Xiaoguang Yang, Jianzhong Zhang

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

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

Recommendations

• scientific article; zbMATH DE number 1163718
• To improve the communication delay by upgrading nodes in a continuous version
• Network upgrading problems
• Approximation algorithms for certain network improvement problems
• Improving spanning trees by upgrading nodes

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximation algorithms for certain network improvement problems
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• Improving spanning trees by upgrading nodes
• Modifying edges of a network to obtain short subgraphs
• Network upgrading problems
• Upgrading bottleneck constrained forests

Cited in

(1)

• To improve the communication delay by upgrading nodes in a continuous version

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

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