The shortest path improvement problems under Hamming distance
Source: Journal of Combinatorial Optimization, Volume 12, Number 4, December 2006 , pp. 351-361(11)
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.
Document Type: Research article
Publication date: 2006-12-01