Competitive Algorithms for Layered Graph Traversal

DOI10.1137/S0097539795279943zbMATH Open0915.68056OpenAlexW2171330236MaRDI QIDQ4210157FDOQ4210157

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)