On minimum cost edge searching

Dariusz Dereniowski; Danny Dyer

doi:10.1016/j.tcs.2013.06.009

On minimum cost edge searching

Abstract

We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not exist in general. On the other hand, we provide a formula for the cost of clearing complete graphs. From our construction it follows that an ideal search strategy of a complete graph does exist and can be calculated efficiently. For general graphs G we give a polynomial-time O(log n)-approximation algorithm for finding minimum cost search strategies. We also prove that recontamination does not help to obtain minimum cost edge search strategies.

Citations

3

CrossRef
0

Web of Science
4

Scopus

Authors (2)

Dariusz Dereniowski prof. dr hab. inż.
Danny Dyer
- Memorial University of Newfoundland Department of Mathematics and Statistics

Cite as

Full text

download paper

downloaded 27 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.tcs.2013.06.009
License: Copyright (2013 Elsevier B.V)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie wyróżnionym w JCR
Published in:: THEORETICAL COMPUTER SCIENCE no. 495, pages 37 - 49,
ISSN: 0304-3975
Language:: English
Publication year:: 2013
Bibliographic description:: Dereniowski D., Dyer D.: On minimum cost edge searching// THEORETICAL COMPUTER SCIENCE. -Vol. 495, (2013), s.37-49
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.tcs.2013.06.009
Verified by:: Gdańsk University of Technology