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

Contents

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.