The shortest path improvement problems under Hamming distance

DOI10.1007/s10878-006-9000-1zbMath1126.90072OpenAlexW1993675440MaRDI QIDQ2385466

Binwu Zhang, Liqun Qi, Zhang, Jianzhong

Publication date: 12 October 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-006-9000-1

zbMATH Keywords

Hamming distanceNP-hardShortest path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Expanding maximum capacity path under weighted sum-type distances ⋮ An algorithm for solving the shortest path improvement problem on rooted trees under unit Hamming distance ⋮ On inverse linear programming problems under the bottleneck-type weighted Hamming distance ⋮ The inverse 1-median problem on tree networks with variable real edge lengths ⋮ Reverse maximum flow problem under the weighted Chebyshev distance ⋮ Further Study on Reverse 1-Center Problem on Trees ⋮ A selfish routing based network improvement problem ⋮ Capacity inverse minimum cost flow problem ⋮ Capacitated partial inverse maximum spanning tree under the weighted Hamming distance ⋮ Efficient algorithms for the reverse shortest path problem on trees under the hamming distance

Cites Work

• Unnamed Item
• On an instance of the inverse shortest paths problem
• Weighted inverse minimum spanning tree problems under Hamming distance
• The center location improvement problem under the Hamming distance
• Computation of the reverse shortest-path problem
• An inverse problem of the weighted shortest path problem
• Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance
• A column generation method for inverse shortest path problems