Competitive Algorithms for Layered Graph Traversal

DOI10.1137/S0097539795279943MaRDI QIDQ4210157zbMATH OpenOpenAlexFDO

Authors Dean P. Foster, Yuval Rabani, Y. Ravid, Amos Fiat, Howard 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)

Recommendations

• scientific article; zbMATH DE number 437566
• On Traversing Layered Graphs On-Line
• Traversing Layered Graphs Using the Work Function Algorithm
• Online Graph Exploration: New Results on Old and New Algorithms

Cites work

• scientific article; zbMATH DE number 437566 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 15120 (Why is no real title available?)
• A note on two problems in connexion with graphs
• An optimal on-line algorithm for metrical task system
• Competitive paging algorithms
• Faster algorithms for the shortest path problem
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• On a routing problem
• On convex body chasing
• On the power of randomization in on-line algorithms
• Random walks on weighted graphs and applications to on-line algorithms
• Searching in the plane
• Traversing Layered Graphs Using the Work Function Algorithm

Cited in

(18)

• Better Bounds for Online Line Chasing
• Traversing Layered Graphs Using the Work Function Algorithm
• On Traversing Layered Graphs On-Line
• Layered graph approaches for combinatorial optimization problems
• scientific article; zbMATH DE number 437566 (Why is no real title available?)
• Intuitionistic layered graph logic
• On convex body chasing
• Online Metric Algorithms with Untrusted Predictions
• The \(k\)-server problem
• Metrical service systems with multiple servers
• An iterative procedure for evaluating digraph competitions
• On the two-dimensional cow search problem
• Competitive distributed decision-making
• The beachcombers' problem: walking and searching with mobile robots
• scientific article; zbMATH DE number 1210362 (Why is no real title available?)
• Constructing competitive tours from local information
• Competitive algorithms for the weighted server problem
• Treasure hunt with advice

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

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