Skip navigation
Skip navigation

Online Graph Exploration: New Results on Old and New Algorithms

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]

dc.contributor.authorMegow, Nicole
dc.contributor.authorMehlhorn, Kurt
dc.contributor.authorSchweitzer, Pascal
dc.coverage.spatialZurich Switzerland
dc.date.accessioned2015-12-10T22:53:03Z
dc.date.createdJuly 4-8 2011
dc.identifier.isbn9783642220111
dc.identifier.urihttp://hdl.handle.net/1885/59195
dc.description.abstractWe 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 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.
dc.publisherSpringer
dc.relation.ispartofseriesInternational Colloquium on Automata, Languages and Programming (ICALP 2011)
dc.sourceProceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)
dc.source.urihttp://dl.acm.org/citation.cfm?id=2027272
dc.subjectKeywords: Arbitrary graphs; Competitive algorithms; Competitive analysis; Competitive ratio; Depth first search; General graph; Graph exploration; Local information; Lower bounds; New results; On-line algorithms; Planar graph; Theoretical computer science; Undirect Competitive analysis; Graph exploration; Online algorithms
dc.titleOnline Graph Exploration: New Results on Old and New Algorithms
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2011
local.identifier.absfor080201 - Analysis of Algorithms and Complexity
local.identifier.ariespublicationU3594520xPUB478
local.type.statusPublished Version
local.contributor.affiliationMegow, Nicole, Max-Planck-Institut fur Informatik
local.contributor.affiliationMehlhorn, Kurt, Max Planck Institute
local.contributor.affiliationSchweitzer, Pascal, College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.startpage478
local.bibliographicCitation.lastpage489
local.identifier.doi10.1016/j.tcs.2012.06.034
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
dc.date.updated2016-02-24T10:19:14Z
local.identifier.scopusID2-s2.0-84868538324
local.identifier.thomsonID000303062800010
CollectionsANU Research Publications

Download

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