Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/29469
Title: The shortest path improvement problems under Hamming distance
Authors: Zhang, B
Zhang, J
Qi, L 
Keywords: Hamming distance
NP-hard
Shortest path problem
Issue Date: 2006
Source: Journal of combinatorial optimization, 2006, v. 12, no. 4, p. 351-361 How to cite?
Journal: Journal of Combinatorial Optimization 
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.
URI: http://hdl.handle.net/10397/29469
ISSN: 1382-6905
DOI: 10.1007/s10878-006-9000-1
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

12
Last Week
0
Last month
0
Citations as of Aug 13, 2017

WEB OF SCIENCETM
Citations

7
Last Week
0
Last month
0
Citations as of Aug 12, 2017

Page view(s)

33
Last Week
2
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.