Competitive Algorithms for Layered Graph Traversal

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, .. ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor. >

Authors

• Amos Fiat
• Dean P. Foster
• Howard J. Karloff
• Yuval Rabani
• Yiftach Ravid
• Sundar Vishwanathan

Keywords

• Computer science
• Costs
• Partitioning algorithms
• Mathematics
• Vents
• Shortest path problem
• Length measurement
• Algorithm design and analysis
• Competitive Algorithm
• Graph Traversal
• Layered Graph
• Lower Bound
• Path Length
• End Stage
• Shortest Path
• End Of Phase
• Service System
• Final Layer
• Edge Length
• Root Of The Tree
• Configuration Space
• Start Of Phase
• Random Graph
• Linear Graph
• Online Algorithm
• Induction Hypothesis
• Proof Sketch
• Department Of Computer Science