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 -