The shortest path improvement problems under Hamming distance

Binwu Zhang; Jianzhong Zhang; Liqun Qi

doi:10.1007/s10878-006-9000-1

The shortest path improvement problems under Hamming distance

Binwu Zhang, Jianzhong Zhang, Liqun Qi

Research output: Journal article publication › Journal article › Academic research › peer-review

18 Citations (Scopus)

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.

Original language	English
Pages (from-to)	351-361
Number of pages	11
Journal	Journal of Combinatorial Optimization
Volume	12
Issue number	4
DOIs	https://doi.org/10.1007/s10878-006-9000-1
Publication status	Published - 1 Dec 2006

Keywords

Hamming distance
NP-hard
Shortest path problem

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

More information

10.1007/s10878-006-9000-1

Cite this

@article{983fc86397394d10a8e21b0712421f37,

title = "The shortest path improvement problems under Hamming distance",

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 = "Hamming distance, NP-hard, Shortest path problem",

author = "Binwu Zhang and Jianzhong Zhang and Liqun Qi",

year = "2006",

month = dec,

day = "1",

doi = "10.1007/s10878-006-9000-1",

language = "English",

volume = "12",

pages = "351--361",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - The shortest path improvement problems under Hamming distance

AU - Zhang, Binwu

AU - Zhang, Jianzhong

AU - Qi, Liqun

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

KW - Hamming distance

KW - NP-hard

KW - Shortest path problem

UR - http://www.scopus.com/inward/record.url?scp=33749599188&partnerID=8YFLogxK

U2 - 10.1007/s10878-006-9000-1

DO - 10.1007/s10878-006-9000-1

M3 - Journal article

SN - 1382-6905

VL - 12

SP - 351

EP - 361

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

The shortest path improvement problems under Hamming distance

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this