An inverse problem of the weighted shortest path problem
The paper discusses an inverse problem of the weighted shortest path problem as follows: Given a directed graph \(G(V, A)\), vertices \(a,b\in V\) and a path \(P\) from \(a\) to \(b\), find a weighted length vector \(w\geq 0\) such that \(P\) is a weighted shortest path from \(a\) to \(b\). It is pointed out that all such vectors form a polyhedral cone and a sufficient and necessary condition for vectors to solve the inverse problem is given. By showing algebraic and graphic characters of the extreme directions of the solution cone, the relation between this problem and the minimal cutset problem in graph theory is shown.
- scientific article; zbMATH DE number 815126
- Inverse multi-objective shortest pPath problem under the bottleneck type weighted Hamming distance
- A strongly polynomial algorithm for the inverse shortest arborescence problem
- On an instance of the inverse shortest paths problem
- Complexity of some inverse shortest path lengths problems
- On an instance of the inverse shortest paths problem
- Note on inverse problem with l_ objective function
- Inverse problem of minimum cuts
- Inverse matroid intersection problem
- A strongly polynomial algorithm for the inverse shortest arborescence problem
- Inverse maximum capacity problems
- Inverse optimization in high-speed networks
- Inverse problems of submodular functions on digraphs
- Two general methods for inverse optimization problems
- Calculating some inverse linear programming problems
- On inverse traveling salesman problems
- The shortest path improvement problems under Hamming distance
- Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes
- Inapproximability results for the inverse shortest paths problem with integer lengths and unique shortest paths
- Some inverse optimization problems on network
- Inverse maximum flow and minimum cut problems
- An algorithm for inverse minimum spanning tree problem
- Notes on inverse bin-packing problems
- Inverse Nonlinear Multicommodity Flow Optimization by Column Generation
- A column generation method for inverse shortest path problems
- 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
- Algorithms for inverse optimization problems
- A network flow method for solving some inverse combinatorial optimization problems
- The restricted inverse optimal value problem on shortest path under \(l_1\) norm on trees
- An enhanced Benders decomposition method for unique shortest path routing
- Inverse optimization in semi-definite programs to impute unknown constraint matrices
- Inverse of the Gomory corner relaxation of integer programs
- Hyperpath deletion in directed hypergraphs
- Inverse conic linear programs in Banach spaces
This page was built for publication: An inverse problem of the weighted shortest path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894996)
