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

  • 1 5

    CrossRef

  • 0

    Web of Science

  • 1 3

    Scopus

Autorzy (4)

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

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 79 razy

Publikacje, które mogą cię zainteresować

Zero-Visibility Cops and Robber Game on a Graph

2013

The complexity of zero-visibility cops and robber

2015

The Complexity of Zero-Visibility Cops and Robber

2014
Meta Tagi