The shortest path improvement problems under Hamming distance

Binwu Zhang, Jianzhong Zhang, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)351-361
Number of pages11
JournalJournal of Combinatorial Optimization
Volume12
Issue number4
DOIs
Publication statusPublished - 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

Cite this