TY - GEN

T1 - Online graph exploration

T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011

AU - Megow, Nicole

AU - Mehlhorn, Kurt

AU - Schweitzer, Pascal

PY - 2011

Y1 - 2011

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 [23] 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 [23] 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.

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

U2 - 10.1007/978-3-642-22012-8_38

DO - 10.1007/978-3-642-22012-8_38

M3 - Conference contribution

SN - 9783642220111

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 478

EP - 489

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

Y2 - 4 July 2011 through 8 July 2011

ER -