ANTS: Agents on networks, trees, and subgraphs

Abstract

The performance of the vertex ant walk (VAW) method on dynamic graphs, where edges may appear or disappear during the search process, was examined. In particular, it was proven that if a certain spanning subgraph S is stable during the period of covering, then the VAW method is guaranteed to cover the graph within time nds, where ds is the diameter of S. Also, if a failure occurs on each edge with probability p, then the expected cover time is bounded from above by nd((log Δ/log(1/p))+((1+p)/(1-p))), where Δ is the maximum vertex degree in the graph. Finally, if G is a static tree, then it is covered within time 2n.