Record Details

Competitive algorithms for layered graph traversal

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Competitive algorithms for layered graph traversal
 
Creator FIAT, A
FOSTER, DP
KARLOFF, H
RABANI, Y
RAVID, Y
VISHWANATHAN, S
 
Subject online algorithms
server
competitive analysis
layered graphs
search strategies
 
Description A layered graph is a connected graph whose vertices are partitioned into sets L-0 = {s}, L-1; L-2,..., and whose edges, which have nonnegative integral weights, run between consecutive layers. Its width is max{\L-i\}. In the on-line 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. We give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. We give a deterministic on-line algorithm which is O(9(w))-competitive on width-w graphs and prove that for no w can a deterministic on-line algorithm have a competitive ratio better than 2(w?2) on width-w graphs. We prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized on-line layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, we give a randomized on-line algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.
 
Publisher SIAM PUBLICATIONS
 
Date 2011-08-29T04:41:23Z
2011-12-26T12:58:24Z
2011-12-27T05:48:16Z
2011-08-29T04:41:23Z
2011-12-26T12:58:24Z
2011-12-27T05:48:16Z
1998
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 28(2), 448-463
0097-5397
http://dspace.library.iitb.ac.in/xmlui/handle/10054/11960
http://hdl.handle.net/10054/11960
 
Language en