Abstrakt

The work contains results regarding two problems posed to a group of mobile entities, called agents, and a survey of fields of research from which these problems originate. First, in the heterogeneous graph searching problem, the agents, also called searchers, are asked to find a fugitive in a graph with edges accessible only to specific types of agents. The rules of the edge searching problem are augmented by introducing labels for the edges of the graph and agents. We provide an example with 3 distinct labels which shows the problem to be non-monotone. The heterogeneous tree searching problem is proved to be NP-Hard. Moreover, it remains NP-Complete even when restricted to monotone strategies. Additionally, an example of a case when the problem admits a polynomial algorithm is provided. In the second problem the agents are asked to complete gossiping in a tree network. The network is an edge-weighted tree and the data can only spread by being carried by agents themselves. In order to traverse an edge, an agent needs to spend energy from its battery, and agents can exchange energy whenever they meet. The bulk of the work consists of a proof that an optimal gossiping strategy can be composed of an optimal convergcast strategy followed by a broadcast strategy. We show that k agents in a network of n nodes can solve this problem in O(k2n2) time.

Autor (1)