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

✍ Scribed by Saurabh Srivastava; R.K. Ghosh

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 290 KB
• Volume: 88
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00365-x

✦ Synopsis

A k-core C k of a tree T is subtree with exactly k leaves for k n l , 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.