The shortest path improvement problems under Hamming distance

Authors: Zhang, Binwu¹; Zhang, Jianzhong²; Qi, Liqun³

Source: Journal of Combinatorial Optimization, Volume 12, Number 4, December 2006 , pp. 351-361(11)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

In this paper, we consider the shortest path improvement problems under Hamming distance (SPIH), where the weights of edges can be modified only within given intervals. Two models are considered: the general SPIH problem and the SPIH problem with a single pair of required vertices. For the first problem, we show that it is strongly NP-hard. For the second problem, we show that even if the network is a chain network, it is still NP-hard.

Keywords: Shortest path problem; NP-hard; Hamming distance

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10878-006-9000-1

Affiliations: 1: Email: bwzhang71@163.com 2: Email: mazhang@cityu.edu.hk 3: Email: maqilq@inet.polyu.edu.hk

Publication date: 2006-12-01