Online graph exploration: New results on old and new algorithms

Nicole Megow, Kurt Mehlhorn, Pascal Schweitzer*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    35 Citations (Scopus)

    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 (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.

    Original languageEnglish
    Pages (from-to)62-72
    Number of pages11
    JournalTheoretical Computer Science
    Volume463
    DOIs
    Publication statusPublished - 7 Dec 2012

    Fingerprint

    Dive into the research topics of 'Online graph exploration: New results on old and new algorithms'. Together they form a unique fingerprint.

    Cite this