Competitive Algorithms for Layered Graph Traversal
From MaRDI portal
Publication:4210157
DOI10.1137/S0097539795279943zbMath0915.68056MaRDI QIDQ4210157
Yuval Rabani, Dean P. Foster, Amos Fiat, Y. Ravid, Howard J. Karloff
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Related Items
On convex body chasing, Constructing competitive tours from local information, Competitive algorithms for the weighted server problem, Competitive distributed decision-making
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