An algorithm for solving the shortest path improvement problem on rooted trees under unit Hamming distance

DOI10.1007/s10957-018-1221-9zbMath1394.90505OpenAlexW2787763202MaRDI QIDQ1670106

Chunyuan He, Panos M. Pardalos, Binwu Zhang, Xiucui Guan

Publication date: 4 September 2018

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-018-1221-9

zbMATH Keywords

dynamic programmingHamming distanceshortest path problemrooted treesnetwork improvement problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

Expanding maximum capacity path under weighted sum-type distances ⋮ Optimal algorithms for inverse obnoxious center location problems under the weighted Chebyshev and Hamming cost norms on networks ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance

Uses Software

• Matlab

Cites Work

• Unnamed Item
• Inverse 1-median problem on trees under weighted Hamming distance
• Inverse min-max spanning tree problem under the weighted sum-type Hamming distance
• Inverse minimum cost flow problems under the weighted Hamming distance
• On an instance of the inverse shortest paths problem
• Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector
• 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
• Inverse combinatorial optimization: a survey on problems, methods, and results
• The shortest path improvement problems under Hamming distance
• Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance
• Some inverse optimization problems under the Hamming distance
• A column generation method for inverse shortest path problems