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

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

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

• 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
• 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?)
• 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

(20)

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

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)