Wyszukiwarka
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)
-
Oznur Yasar Diner
- Kadir Has University Department of Information Technology
-
Danny Dyer
- Memorial University of Newfoundland Department of Mathematics and Statistics
Cytuj jako
Pełna treść
pobierz publikację
pobrano 29 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2013.03.004
- Licencja
- Copyright (2013 Elsevier B.V)
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 361 razy
Publikacje, które mogą cię zainteresować
Bounds on the vertex-edge domination number of a tree
- B. Krishnakumari,
- Y. B. Venkatakrishnan,
- M. Krzywkowski
2014