Zero-visibility cops and robber and the pathwidth of a graph - Publikacja - MOST Wiedzy

Wyszukiwarka

Zero-visibility cops and robber and the pathwidth of a graph

Abstrakt

We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility copnumber can be bounded both above and below by positive multiples of the pathwidth.

Cytowania

  • 8

    CrossRef

  • 5

    Web of Science

  • 7

    Scopus

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
JOURNAL OF COMBINATORIAL OPTIMIZATION nr 29, wydanie 3, strony 541 - 564,
ISSN: 1382-6905
Język:
angielski
Rok wydania:
2015
Opis bibliograficzny:
Dereniowski D., Dyer D., Tifenbach R., Yang B.: Zero-visibility cops and robber and the pathwidth of a graph // JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 29, iss. 3 (2015), s.541-564
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-014-9712-6
Weryfikacja:
Politechnika Gdańska

wyświetlono 18 razy

Publikacje, które mogą cię zainteresować

Meta Tagi