Searching by heterogeneous agents

Dariusz Dereniowski , Łukasz Kuszner , Robert Ostrowski


In this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs. In such setting a searcher, once a search strategy initially decides on the label of the searcher, can be present on an edge only if the label of the searcher and the label of the edge are the same. We prove that such searching problem is not monotone even for trees and moreover we give instances in which the number of recontamination events is Ω(n2), where n is the size of a tree. Another negative result regards the NP-completeness of the monotone heterogeneous search in trees. The two above properties show that this problem behaves very differently from the classical edge search. On the other hand, if all edges of a particular label form a (connected) subtree of the input tree, then we show that optimal heterogeneous search strategy can be computed efficiently.
Author Dariusz Dereniowski
Dariusz Dereniowski,,
, Łukasz Kuszner (FMPI / II)
Łukasz Kuszner ,,
- Institute of Informatics
, Robert Ostrowski
Robert Ostrowski,,
Publication size in sheets0.6
Book Heggernes Pinar (eds.): Algorithms and complexity: 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019: proceedings, Lecture Notes In Computer Science, no. 11485, 2019, Springer International Publishing, ISBN 978-3-030-17401-9, [978-3-030-17402-6], 378 p., DOI:10.1007/978-3-030-17402-6
Keywords in Englishgraph searching, mobile agent computing, monotonicity, pursuit-evasion
Languageen angielski
Score (nominal)20
Score sourcepublisherList
ScoreMinisterial score = 20.0, 17-11-2019, ChapterFromConference
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?