Optimal graph exploration without good maps

Anders Dessmark, A. Pelc

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

    18 Citations (SciVal)

    Abstract

    A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class
    Original languageEnglish
    Title of host publicationAlgorithms - ESA 2002. 10th Annual European Symposium. Proceedings (Lecture Notes in Computer Science Vol.2461)
    PublisherSpringer
    Pages374-386
    Volume2461
    ISBN (Print)3-540-44180-8
    Publication statusPublished - 2002
    EventAlgorithms - ESA 2002. 10th Annual European Symposium. Proceedings - Rome, Italy
    Duration: 2002 Sep 172002 Sep 21

    Publication series

    Name
    Volume2461

    Conference

    ConferenceAlgorithms - ESA 2002. 10th Annual European Symposium. Proceedings
    Country/TerritoryItaly
    CityRome
    Period2002/09/172002/09/21

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • natural exploration algorithms
    • undirected connected graph
    • optimal graph exploration
    • lower bounds
    • edge traversals
    • robot

    Fingerprint

    Dive into the research topics of 'Optimal graph exploration without good maps'. Together they form a unique fingerprint.

    Cite this