An algorithm for ranking quickest simple paths

DOI10.1016/S0305-0548(03)00250-8zbMath1077.90075MaRDI QIDQ1886854

Marta M. B. Pascoal, Joao Carlos Namorado Climaco, Maria Eugénia Captivo

Publication date: 19 November 2004

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

Graph theory; Network; Quickest path; Simple path; Paths ranking

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Spare routing problem with \(p\) minimal paths for time-based stochastic flow networks, A method to evaluate routing policy through \(p\) minimal paths for stochastic case, System reliability for quickest path problems under time threshold and budget, Internet packet routing: application of a \(K\)-quickest path algorithm, Computational experiments with a lazy version of a \(K\) quickest simple path ranking algorithm, On transmission time through \(k\) minimal paths of a capacitated-flow network, Time version of the shortest path problem in a stochastic-flow network, Calculation of minimal capacity vectors through \(k\) minimal paths under budget and time constraints, A comprehensive survey on the quickest path problem

Cites Work

• A note on two problems in connexion with graphs
• The quickest path problem
• Algorithms for the quickest path problem and the enumeration of quickest paths
• An algorithm for finding the \(k\) quickest paths in a network
• On the quickest path problem
• Finding the \(k\) quickest simple paths in a network
• An algorithm for the quickest path problem
• An efficient algorithm for K shortest simple paths
• Finding the K Shortest Loopless Paths in a Network