Distributed algorithms for finding and
maintaining a k-tree core in a dynamic network

**Abstract**

A k-core C_{k} of a tree T is subtree with exactly k leaves
for k ≤ n,
where n _{l} the number of leaves in T, and minimizes the sum of the
distances of all nodes from C_{k}. In this paper first we propose a
distributed algorithm for constructing a rooted spanning tree of a
dynamic graph such that root of the tree is located near the center
of the graph. Then we provide a distributed algorithm for finding
k-core of that spanning tree. The spanning tree is constructed in two
stages. In the first stage, a forest of trees is generated. In the
next stage these trees are connected to form a single rooted tree. An
interesting aspect of the first stage of proposed spanning algorithm
is that it implicitly constructs the (convex) hull of those nodes
which are not already included in the spanning forest. The process is
repeated till all non root nodes of the graph have chosen a unique
parent. We implemented the algorithms for finding spanning tree and
its k-core. A core can be quite useful for routing messages in a
dynamic network consisting of a set of mobile devices.

[
Postscript |
PDF
] © 2008