Search
Abstract
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.
Citations
-
9
CrossRef
-
0
Web of Science
-
9
Scopus
Authors (3)
-
Oznur Yasar Diner
- Kadir Has University Department of Information Technology
-
Danny Dyer
- Memorial University of Newfoundland Department of Mathematics and Statistics
Cite as
Full text
download paper
downloaded 25 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.03.004
- License
- Copyright (2013 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 161,
edition 13-14,
pages 1950 - 1958,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2013
- Bibliographic description:
- Dereniowski D., Yasar Diner O., Dyer D.: Three-fast-searchable graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 161, iss. 13-14 (2013), s.1950-1958
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2013.03.004
- Verified by:
- Gdańsk University of Technology
seen 355 times
Recommended for you
Bounds on the vertex-edge domination number of a tree
- B. Krishnakumari,
- Y. B. Venkatakrishnan,
- M. Krzywkowski
2014