TY - JOUR

T1 - Online graph exploration

T2 - New results on old and new algorithms

AU - Megow, Nicole

AU - Mehlhorn, Kurt

AU - Schweitzer, Pascal

PY - 2012/12/7

Y1 - 2012/12/7

N2 - We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs (Constructing competitive tours from local information, Theoretical Computer Science 130, pp. 125-138, 1994) proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs. While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus. Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights.

AB - We study the problem of exploring an unknown undirected connected graph. Beginning in some start vertex, a searcher must visit each node of the graph by traversing edges. Upon visiting a vertex for the first time, the searcher learns all incident edges and their respective traversal costs. The goal is to find a tour of minimum total cost. Kalyanasundaram and Pruhs (Constructing competitive tours from local information, Theoretical Computer Science 130, pp. 125-138, 1994) proposed a sophisticated generalization of a Depth First Search that is 16-competitive on planar graphs. While the algorithm is feasible on arbitrary graphs, the question whether it has constant competitive ratio in general has remained open. Our main result is an involved lower bound construction that answers this question negatively. On the positive side, we prove that the algorithm has constant competitive ratio on any class of graphs with bounded genus. Furthermore, we provide a constant competitive algorithm for general graphs with a bounded number of distinct weights.

KW - Competitive analysis

KW - Graph exploration

KW - Online algorithms

UR - http://www.scopus.com/inward/record.url?scp=84868538324&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.06.034

DO - 10.1016/j.tcs.2012.06.034

M3 - Article

AN - SCOPUS:84868538324

SN - 0304-3975

VL - 463

SP - 62

EP - 72

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -