Three-fast-searchable graphs
Loading...
Date
2013
Authors
Dereniowski, Dariusz
Diner, Öznur Yaşar
Dyer, Danny
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier Science Bv
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 vertical bar E(G)vertical bar 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. (C) 2013 Elsevier B.V. All rights reserved.
Description
Keywords
Computational complexity, Fast searching, Graph searching
Turkish CoHE Thesis Center URL
Citation
5
WoS Q
Q3
Scopus Q
Q2
Source
Volume
161
Issue
13-14
Start Page
1950
End Page
1958