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

DOI10.1016/J.TCS.2022.11.017MaRDI QIDQ2680863zbMATH OpenOpenAlexFDO

Authors 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

Canadian traveller problemmaximum cutsonline algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• 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
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• The Canadian Traveller Problem and its competitive analysis

Cites work

• A note on the k-Canadian traveller problem
• A note on two problems in connexion with graphs
• An \(\mathrm{AO}^{*}\) based exact algorithm for the Canadian traveler problem
• An optimal randomized online algorithm for the \(k\)-Canadian traveller problem on node-disjoint paths
• Approximating the Canadian traveller problem with online randomization
• scientific article; zbMATH DE number 432827 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• 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
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• On the randomized online strategies for the \(k\)-Canadian traveler problem
• Shortest paths without a map
• The Canadian Traveller Problem and its competitive analysis
• The covering Canadian traveller problem

Cited in

(6)

• The Canadian Traveller Problem and its competitive analysis
• Approximation and complexity of multi-target graph search and the Canadian traveler problem
• Improved deterministic strategy for the Canadian Traveller Problem exploiting small max-\((s,t)\)-cuts
• On the online multi-agent O-D \(k\)-Canadian traveler problem
• The Canadian traveller problem on outerplanar graphs
• The Canadian traveller problem on unit-weighted and arbitrarily weighted outerplanar graphs

This page was built for publication: The influence of maximum \((s,t)\)-cuts on the competitiveness of deterministic strategies for the Canadian traveller problem

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