Skip navigation
Skip navigation

Online Graph Exploration: New Results on Old and New Algorithms

Megow, Nicole; Mehlhorn, Kurt; Schweitzer, Pascal


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...[Show more]

CollectionsANU Research Publications
Date published: 2011
Type: Conference paper
Source: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)
DOI: 10.1016/j.tcs.2012.06.034


File Description SizeFormat Image
01_Megow_Online_Graph_Exploration:_New_2011.pdf250.22 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator