10/26/2006

Speaker(s) : Morten Mjede (Bergen University)

The k-packing problem asks for a subset S of the nodes in a graph such that the distance between any pair of nodes in S is greater than k. This problem has applications to placing facilities in a network. In the current paper we present a self-stabilizing algorithm for computing a maximal k-packing in a general graph. Our algorithm uses a constant number of variables per node. This improves the memory requirement compared to the previous most memory efficient algorithm which used k variables per node.