Three-fast-searchable graphs

Loading...
Thumbnail Image

Date

2013

Authors

Dereniowski, Dariusz
Diner, Öznur Yaşar
Dyer, Danny

Journal Title

Journal ISSN

Volume Title

Publisher

Elsevier Science Bv

Research Projects

Organizational Units

Journal Issue

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