The shortest path improvement problems under Hamming distance |
| |
| Authors: | Binwu Zhang Jianzhong Zhang Liqun Qi |
| |
| Institution: | (1) Department of Mathematics and Physics, Hohai University, Changzhou Campus, Changzhou, 213022, China;(2) Department of System Engineering and Engineering Manegement, The Chinese University of Hong Kong, Hong Kong, China;(3) Department of Mathematics, Hong Kong Polytechnic University, Hong Kong, China |
| |
| 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.This paper is dedicated to Dr. Yong He. |
| |
| Keywords: | Shortest path problem NP-hard Hamming distance |
| 本文献已被 SpringerLink 等数据库收录！ |
|
