Complexity of some inverse shortest path lengths problems

DOI10.1002/NET.20344MaRDI QIDQ3057164zbMATH OpenOpenAlexFDO

Authors Tingting Cui, Dorit S. Hochbaum

Publication date 24 November 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20344

zbMATH Keywords

complexityinverse optimizationpolynomial algorithmshortest path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1341907
• Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths
• scientific article; zbMATH DE number 1086909
• scientific article; zbMATH DE number 815126
• Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values

Cites work

• A Faster Algorithm for the Inverse Spanning Tree Problem
• A network improvement problem under different norms
• A Polynomial Barrier Algorithm for Linearly Constrained Convex Programming Problems
• Efficient Algorithms for the Inverse Spanning-Tree Problem
• Finding optimum branchings
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 3307153 (Why is no real title available?)
• Inapproximability and a polynomially solvable special case of a network improvement problem.
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Inverse matroid intersection problem
• Inverse Optimization
• On an instance of the inverse shortest paths problem
• On the use of an inverse shortest paths algorithm for recovering linearly correlated costs
• Solving inverse spanning tree problems through network flow techniques
• Some reverse location problems
• The complexity analysis of the inverse center location problem
• The inverse optimal value problem

Cited in

(17)

• On an instance of the inverse shortest paths problem
• Searching for realizations of finite metric spaces in tight spans
• An inverse problem of the weighted shortest path problem
• Combinatorial algorithms for solving the restricted bounded inverse optimal value problem on minimum spanning tree under weighted l_ norm
• Complexity of inverse shortest path routing
• On the complexity of finding paths in a two-dimensional domain I: Shortest paths
• scientific article; zbMATH DE number 3876620 (Why is no real title available?)
• Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths
• scientific article; zbMATH DE number 1341907 (Why is no real title available?)
• scientific article; zbMATH DE number 1086909 (Why is no real title available?)
• Reverse maximum flow problem under the weighted Chebyshev distance
• scientific article; zbMATH DE number 1932373 (Why is no real title available?)
• scientific article; zbMATH DE number 815126 (Why is no real title available?)
• Efficient algorithms for the reverse shortest path problem on trees under the Hamming distance
• On reverse shortest paths in geometric proximity graphs
• The restricted inverse optimal value problem on shortest path under \(l_1\) norm on trees
• A combinatorial algorithm for inverse continuous quadratic knapsack problem

This page was built for publication: Complexity of some inverse shortest path lengths problems

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