Three-fast-searchable graphs - Publication - Bridge of Knowledge

Search

Three-fast-searchable graphs

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)

Cite as

Full text

download paper
downloaded 0 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 313 times

Recommended for you

Meta Tags