Computing shortest paths with uncertainty

DOI10.1016/J.JALGOR.2004.07.005zbMATH Open1115.68111OpenAlexW2041077764MaRDI QIDQ3437091FDOQ3437091

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

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

zbMATH Keywords

shortest path

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• A robust optimization approach with probe-able uncertainty
• 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)