Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem

DOI10.1007/978-3-642-04802-9_11zbMath1184.90030OpenAlexW1804374324MaRDI QIDQ3557808

Jacek Czekaj, Leslaw Socha

Publication date: 23 April 2010

Published in: IFIP Advances in Information and Communication Technology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04802-9_11

zbMATH Keywords

complexitysecond moment criterion

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15)

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function
• A label correcting approach for solving bicriterion shortest-path problems
• On a routing problem
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Efficient Algorithms for Shortest Paths in Sparse Networks
• State space partitioning methods for stochastic shortest path problems
• A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems
• Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-linear Objectives with Applications

This page was built for publication: Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem