ALCOMFT-TR-01-138

J. Petit
Hamiltonian cycles in faulty random geometric networks
Barcelona. Work package 2. June 2001.

Abstract: In this paper we analyze the Hamiltonian properties of faulty random networks. This consideration is of interest when considering wireless broadcast networks. A random geometric network is a graph whose vertices correspond to points uniformly and independently distributed in the unit square, and whose edges connect any pair of vertices if their distance is below some specified bound. A faulty random geometric network is a random geometric network whose vertices or edges fail at random. Algorithms to find Hamiltonian cycles in faulty random geometric networks are presented.

Postscript file: ALCOMFT-TR-01-138.ps.gz (170 kb).