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

DOI10.1007/S10957-018-1221-9zbMATH Open1394.90505OpenAlexW2787763202MaRDI QIDQ1670106FDOQ1670106

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

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

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)

Cites Work

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

Cited In (11)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Improvement of shortest path of arborescent network in the case of Hamming distance
• Algorithms for the shortest path improvement problems under unit Hamming distance
• The complexity analysis of the shortest path improvement problem under the Hamming distance
• Efficient algorithms for the reverse shortest path problem on trees under the Hamming distance
• Maximum shortest path interdiction problem by upgrading edges on trees under 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

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)