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

DOI10.1007/S10957-018-1221-9MaRDI QIDQ1670106zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Algorithms for the shortest path improvement problems under unit Hamming distance
• scientific article; zbMATH DE number 5631939
• Efficient algorithms for the reverse shortest path problem on trees under the Hamming distance
• An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance
• The shortest path improvement problems under Hamming distance
• The complexity analysis of the shortest path improvement problem under the Hamming distance
• Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance
• Improvement of shortest path of arborescent network in the case of Hamming distance
• scientific article; zbMATH DE number 2080243
• A near-optimal algorithm for finding an optimal shortcut of a tree

Cites work

• A column generation method for inverse shortest path problems
• Computation of the reverse shortest-path problem
• Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance
• Inverse 1-median problem on trees under weighted Hamming distance
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector
• 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
• Some inverse optimization problems under the Hamming distance
• The center location improvement problem under the Hamming distance
• The complexity analysis of the shortest path improvement problem under the Hamming distance
• The shortest path improvement problems under Hamming distance
• Weighted inverse minimum spanning tree problems under Hamming distance

Cited in

(11)

• Expanding maximum capacity path under weighted sum-type distances
• scientific article; zbMATH DE number 5631939 (Why is no real title available?)
• scientific article; zbMATH DE number 2080243 (Why is no real title available?)
• The complexity analysis of the shortest path improvement problem under the Hamming distance
• Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance
• Improvement of shortest path of arborescent network in the case of Hamming distance
• The shortest path improvement problems under Hamming distance
• An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance
• Algorithms for the shortest path improvement problems under unit Hamming distance
• Efficient algorithms for the reverse shortest path problem on trees under the Hamming distance
• Optimal algorithms for inverse obnoxious center location problems under the weighted Chebyshev and Hamming cost norms on networks

Describes a project that uses

Uses Software

• Matlab

This page was built for publication: An algorithm for solving the shortest path improvement problem on rooted trees under unit Hamming distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1670106)