Online Graph Exploration: New Results on Old and New Algorithms
-
Altmetric Citations
Megow, Nicole; Mehlhorn, Kurt; Schweitzer, Pascal
Description
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]
Collections | ANU Research Publications |
---|---|
Date published: | 2011 |
Type: | Conference paper |
URI: | http://hdl.handle.net/1885/59195 |
Source: | Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011) |
DOI: | 10.1016/j.tcs.2012.06.034 |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
01_Megow_Online_Graph_Exploration:_New_2011.pdf | 250.22 kB | Adobe PDF | Request a copy |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator