Finding a princess in a palace: a pursuit-evasion problem (Q1953406)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Finding a princess in a palace: a pursuit-evasion problem
scientific article

    Statements

    Finding a princess in a palace: a pursuit-evasion problem (English)
    0 references
    0 references
    0 references
    7 June 2013
    0 references
    Summary: This paper solves a pursuit-evasion problem in which a prince must find a princess who is constrained to move on each day from one vertex of a finite graph to another. Unlike the related and much studied `cops and robbers game', the prince has no knowledge of the position of the princess; he may, however, visit any single room he wishes on each day. We characterize the graphs for which the prince has a winning strategy, and determine, for each such graph, the minimum number of days the prince requires to guarantee to find the princess.
    0 references
    combinatorial search
    0 references
    pursuit-evasion
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references