Journal
NETWORKS
Volume 47, Issue 2, Pages 72-80Publisher
WILEY
DOI: 10.1002/net.20097
Keywords
dynamic programming; minimax objective; graph diameter; graph radius; arc upgrading; tree graphs; heuristics
Ask authors/readers for more resources
In transportation and telecommunication systems, the performance of the underlying network can often be improved by upgrading some of the arcs in the network. If an arc is upgraded, the travel time along this arc is reduced by a discount factor alpha, 0 <= alpha <= 1. With respect to different minimax network objectives, we define a series of problems that involve finding the best q arcs in a network to upgrade. We show that these problems are NP-hard on general graphs, but polynomially solvable on trees. Finally, we compare three heuristic solution approaches for complete graphs based on these polynomial results and find one to far outperform the others. (c) 2005 Wiley Periodicals, Inc.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available