Computing shortest paths with uncertainty

DOI10.1016/J.JALGOR.2004.07.005MaRDI QIDQ3437091zbMATH OpenOpenAlexFDO

Authors Liadan O'Callaghan, Chris Olston, Rina Panigrahy, Tomás Feder, Rajeev Motwani

Publication date 14 May 2007

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jalgor.2004.07.005

zbMATH Keywords

shortest path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1962828
• Uncertain random shortest path problem
• Shortest path problem with uncertain arc lengths
• Finding reliable shortest paths in road networks under uncertainty
• Algorithms and uncertainty sets for data-driven robust shortest path problems
• Computing almost shortest paths
• Constrained shortest path with uncertain transit times
• Shortest path methods: A unifying approach
• scientific article; zbMATH DE number 7093019
• Finding the shortest path in stochastic networks

Cited in

(24)

• Scheduling with testing on multiple identical parallel machines
• Query-competitive algorithms for cheapest set problems under uncertainty
• Scheduling with a processing time oracle
• The power of amortization on scheduling with explorable uncertainty
• Query-Competitive Sorting with Uncertainty.
• The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
• Algorithms for Queryable Uncertainty
• Scheduling with explorable uncertainty
• Explorable uncertainty in scheduling with non-uniform testing times
• An adversarial model for scheduling with testing
• Shortest path problem with uncertain arc lengths
• A robust optimization approach with probe-able uncertainty
• scientific article; zbMATH DE number 1962828 (Why is no real title available?)
• Computing shortest paths in the plane with removable obstacles
• Query-competitive sorting with uncertainty
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
• Combinatorial optimization in system configuration design
• Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
• Query minimization under stochastic uncertainty
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• Randomization helps computing a minimum spanning tree under uncertainty
• Round-competitive algorithms for uncertainty problems with parallel queries
• Optimal path discovery problem with homogeneous knowledge
• Two-stage robust optimization problems with two-stage uncertainty

This page was built for publication: Computing shortest paths with uncertainty

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