Complexity of Canadian traveler problem variants

DOI10.1016/j.tcs.2013.03.016zbMath1277.68087DBLPjournals/tcs/FriedSBW13arXiv1207.4710OpenAlexW2009831508WikidataQ57518721 ScholiaQ57518721MaRDI QIDQ386993

Amit Benbassat, Solomon Eyal Shimony, Cenny Wenner, Dror Fried

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.4710

zbMATH Keywords

Canadian traveler problemcomplexity of navigation under uncertaintystochastic shortest path with recourse

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Approximating the Canadian traveller problem with online randomization ⋮ An AO^* Based Exact Algorithm for the Canadian Traveler Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest paths without a map
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• Repeated-task Canadian Traveler Problem
• Stochastic shortest path problems with recourse

This page was built for publication: Complexity of Canadian traveler problem variants