Three-fast-searchable graphs - Publikacja - MOST Wiedzy

Wyszukiwarka

Three-fast-searchable graphs

Abstrakt

In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates a larger number of searchers. We examine this model, and characterize graphs for which 2 or 3 searchers are sufficient. We prove that the corresponding decision problem is NP-complete.

Cytowania

  • 9

    CrossRef

  • 0

    Web of Science

  • 9

    Scopus

Autorzy (3)

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
DISCRETE APPLIED MATHEMATICS nr 161, wydanie 13-14, strony 1950 - 1958,
ISSN: 0166-218X
Język:
angielski
Rok wydania:
2013
Opis bibliograficzny:
Dereniowski D., Yasar Diner O., Dyer D.: Three-fast-searchable graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 161, iss. 13-14 (2013), s.1950-1958
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2013.03.004
Weryfikacja:
Politechnika Gdańska

wyświetlono 356 razy

Publikacje, które mogą cię zainteresować

Meta Tagi