Competitive algorithms for layered graph traversal
Competitive algorithms for layered graph traversal
复制标题
分层图遍历的竞争算法
DOI：
10.1109/sfcs.1991.185381
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
S. Vishwanathan
中科院分区：
文献类型：
--
作者：
A. Fiat;Dean Phillips Foster;H. Karloff;Y. Rabani;Yiftach Ravid;S. Vishwanathan
分层图是一个连接的加权图，其顶点被划分为l/sub 0/=（s），l/sub 1/，l/sub 2/，。 。 。，其边缘在连续的层之间。它的宽度是最大（mod l/ sub i/ mod）。在在线分层的图形遍历问题中，搜索器以s的宽度宽度图开始，并试图达到目标顶点t。但是，仅当搜索者到达I-1层时，第I层的顶点和I-1层之间的边缘才会被揭示。作者在分层图遍历算法的竞争比率上给出了上限和下限。他们给出了确定性的在线算法，该算法是O（9W）对宽度W图的竞争性，并证明没有W可以确定性的在线算法的竞争比率优于2W/ sup -2/ width-W图。他们证明，对于所有W/2，在任何随机在线分层遍历遍历算法的竞争比率上都是下限。为了遍历与公共源的W脱节路径组成的分层图，它们给出了具有O（log w）竞争比的随机在线算法，并证明这是最佳的，可以达到恒定因素。<< etx >>
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.<<ETX>>