On-Line Graph Searching by a Smell-Oriented Vertex Process

Israel A. Wagner, Michael Lindenbaum and Alfred M. Bruckstein

An ant walks along the edges of a graph G, occasionaly leaving pheromone traces at vertices, and using those traces to guide its exploration. We show that the ant can cover the graph within time O(nd) where n is the number of vertices and d the diameter of G. The use of traces achieves a tradeoff between random and self-avoiding walks, as it can give lower priority to already visited neighbors. A Hamiitonian cycle in G, if one exists, is a limit cycle of the smell directed graph exploration process.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.