Paper Info
Title
Online graph exploration: new results on old and new algorithms
Abstract
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.
Year
DOI
Venue
2012
10.1016/j.tcs.2012.06.034
Theoretical Computer Science
Keywords
DocType
Volume
Graph exploration,Online algorithms,Competitive analysis
Journal
463,
ISSN
Citations 
PageRank 
0302-9743
21
0.84
References 
Authors
26
3
Name
Order
Citations
PageRank
nicole megow130226.73
Kurt Mehlhorn25314853.36
Pascal Schweitzer321416.94