Computing shortest paths with uncertainty

DOI10.1016/j.jalgor.2004.07.005zbMath1115.68111OpenAlexW2041077764MaRDI QIDQ3437091

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

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

Related Items

Scheduling with testing on multiple identical parallel machines, Two-stage robust optimization problems with two-stage uncertainty, Randomization Helps Computing a Minimum Spanning Tree under Uncertainty, Query-competitive sorting with uncertainty, Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments, Unnamed Item, Round-competitive algorithms for uncertainty problems with parallel queries, Query-competitive algorithms for cheapest set problems under uncertainty, Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty, An adversarial model for scheduling with testing, Algorithms for Queryable Uncertainty, A robust optimization approach with probe-able uncertainty, Query minimization under stochastic uncertainty, Optimal path discovery problem with homogeneous knowledge, Query-Competitive Sorting with Uncertainty., The Minimum Cost Query Problem on Matroids with Uncertainty Areas., Combinatorial optimization in system configuration design, Randomization Helps Computing a Minimum Spanning Tree under Uncertainty, Computing Shortest Paths in the Plane with Removable Obstacles, Scheduling with a processing time oracle, Explorable uncertainty in scheduling with non-uniform testing times