Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values

DOI10.1080/10020070612330048MaRDI QIDQ2455841zbMATH OpenOpenAlexFDO

Authors Longcheng Liu, Yong He

Publication date 26 October 2007

Published in Progress in Natural Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/10020070612330048

zbMATH Keywords

computational complexityinverse problemminimum spanning treereverse problemshortest-path problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Solving inverse spanning tree problems through network flow techniques
• A strongly polynomial algorithm for the inverse shortest arborescence problem
• Inverse Min-Max Spanning Tree Problem Under the Weighted Sum-Type Hamming Distance
• Computation of the reverse shortest-path problem
• Inverse min-max spanning tree problem under the weighted sum-type Hamming distance

Cited in

(8)

• A strongly polynomial algorithm for the inverse shortest arborescence problem
• Computation of the reverse shortest-path problem
• Weighted inverse maximum perfect matching problems under the Hamming distance
• Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes
• Complexity of some inverse shortest path lengths problems
• Efficient algorithms for the reverse shortest path problem on trees under the Hamming distance
• The restricted inverse optimal value problem on shortest path under \(l_1\) norm on trees
• Inverse minimum cost flow problems under the weighted Hamming distance

This page was built for publication: Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values

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