Searching by Heterogeneous Agents - Publikacja - MOST Wiedzy

Wyszukiwarka

Searching by Heterogeneous Agents

Abstrakt

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 Ω(n^2), 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.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
Algorithms and Complexity strony 199 - 211
Język:
angielski
Rok wydania:
2019
Opis bibliograficzny:
Dereniowski D., Kuszner Ł., Ostrowski R.: Searching by Heterogeneous Agents// Algorithms and Complexity/ : , 2019, s.199-211
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-030-17402-6_17
Weryfikacja:
Politechnika Gdańska

wyświetlono 97 razy

Publikacje, które mogą cię zainteresować

Meta Tagi