Contiguous Search Problem in Sierpiński Graphs

Authors: Flaminia L Luccio

Publish Date: 2008/05/30

Volume: 44, Issue: 2, Pages: 186-204

PDF Link

Abstract

In this paper we consider the problem of capturing an intruder in a particular fractal graph the Sierpiński graph SG n The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder The intruder is a mobile entity that escapes from the team of agents moving arbitrarily fast inside the network ie traversing any number of contiguous nodes as long as no other agent resides on them The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SG n We first derive lower bounds on the minimum number of agents number of moves and time steps required to capture the intruder We then consider some variations of the model based on the capabilities of the agents visibility where the agents can “see” the state of their neighbors and thus can move autonomously locality where the agents can only access local information and thus their moves have to be coordinated by a leader For each model we design a capturing strategy and we make some observations One of our goals is to continue a previous study on what is the impact of visibility on complexity in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies However the strategy in the visibility model is fully distributed whereas the other strategy requires a leader Moreover the second strategy requires a higher number of moves and time steps

Keywords: