The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem

DOI10.1016/j.tcs.2022.11.017OpenAlexW4309102287MaRDI QIDQ2680863

Pierre Bergé, Lou Salaün

Publication date: 4 January 2023

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.11.017

zbMATH Keywords

online algorithmsmaximum cutsCanadian traveller problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Shortest paths without a map
• A note on the \(k\)-Canadian traveller problem
• The Canadian Traveller Problem and its competitive analysis
• Improved deterministic strategy for the Canadian Traveller Problem exploiting small max-\((s,t)\)-cuts
• Multiple canadians on the road: minimizing the distance competitive ratio
• On the competitiveness of memoryless strategies for the \(k\)-Canadian traveller problem
• An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• The covering Canadian traveller problem
• Approximating the Canadian traveller problem with online randomization
• An AO^* Based Exact Algorithm for the Canadian Traveler Problem