Competitive Algorithms for Layered Graph Traversal

DOI10.1137/S0097539795279943zbMath0915.68056OpenAlexW2171330236MaRDI QIDQ4210157

Dean P. Foster, Y. Ravid, Yuval Rabani, Amos Fiat, Howard J. Karloff

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795279943

zbMATH Keywords

competitive analysislayered graphssearch strategies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (12)

Constructing competitive tours from local information ⋮ Competitive algorithms for the weighted server problem ⋮ Treasure Hunt with Advice ⋮ Competitive distributed decision-making ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ The \(k\)-server problem ⋮ On convex body chasing ⋮ Metrical service systems with multiple servers ⋮ On the two-dimensional cow search problem ⋮ Intuitionistic Layered Graph Logic ⋮ Better Bounds for Online Line Chasing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Searching in the plane
• On convex body chasing
• On the power of randomization in on-line algorithms
• Random walks on weighted graphs and applications to on-line algorithms
• On a routing problem
• Faster algorithms for the shortest path problem
• Competitive paging algorithms
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• An optimal on-line algorithm for metrical task system
• Traversing Layered Graphs Using the Work Function Algorithm

This page was built for publication: Competitive Algorithms for Layered Graph Traversal