An Algorithm for Solving the Shortest Path Improvement Problem on Rooted Trees Under Unit Hamming Distance

Binwu Zhang (), Xiucui Guan (), Panos M. Pardalos and Chunyuan He
Additional contact information
Binwu Zhang: Hohai University
Xiucui Guan: Southeast University
Panos M. Pardalos: University of Florida
Chunyuan He: Hohai University

Journal of Optimization Theory and Applications, 2018, vol. 178, issue 2, No 11, 538-559

Abstract: Abstract Shortest path problems play important roles in computer science, communication networks, and transportation networks. In a shortest path improvement problem under unit Hamming distance, an edge-weighted graph with a set of source–terminal pairs is given. The objective is to modify the weights of the edges at a minimum cost under unit Hamming distance such that the modified distances of the shortest paths between some given sources and terminals are upper bounded by the given values. As the shortest path improvement problem is NP-hard, it is meaningful to analyze the complexity of the shortest path improvement problem defined on rooted trees with one common source. We first present a preprocessing algorithm to normalize the problem. We then present the proofs of some properties of the optimal solutions to the problem. A dynamic programming algorithm is proposed for the problem, and its time complexity is analyzed. A comparison of the computational experiments of the dynamic programming algorithm and MATLAB functions shows that the algorithm is efficient although its worst-case complexity is exponential time.

Keywords: Shortest path problem; Rooted trees; Network improvement problem; Hamming distance; Dynamic programming; 90C27; 90C35; 90C39 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-018-1221-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:178:y:2018:i:2:d:10.1007_s10957-018-1221-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-018-1221-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().