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 -