Wyszukiwarka
Abstrakt
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.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
4
Scopus
Autorzy (2)
-
Danny Dyer
- Memorial University of Newfoundland Department of Mathematics and Statistics
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2013.06.009
- Licencja
- Copyright (2013 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 495,
strony 37 - 49,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2013
- Opis bibliograficzny:
- Dereniowski D., Dyer D.: On minimum cost edge searching// THEORETICAL COMPUTER SCIENCE. -Vol. 495, (2013), s.37-49
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2013.06.009
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 91 razy
Publikacje, które mogą cię zainteresować
Comparison of reproduction strategies in genetic algorithm approach to graph searching
- Ł. Wrona,
- B. Jaworski