Paper Info
Title
Distributed algorithms for finding and maintaining a k-tree core in a dynamic network
Abstract
A k-core Ck of a tree T is subtree with exactly k leaves for k ≤ nl, where nl the number of leaves in T, and minimizes the sum of the distances of all nodes from Ck. 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.
Year
DOI
Venue
2003
10.1016/S0020-0190(03)00365-X
Inf. Process. Lett.
Keywords
Field
DocType
dynamic network,ad hoc networks,routing,unique parent,distributed algorithms,k-core ck,non root node,dynamic graph,interesting aspect,mobile device,rooted core,k-core,single rooted tree,k-tree core,next stage,convex hull,distributed algorithm,ad hoc network,spanning tree
Discrete mathematics,Combinatorics,Distributed minimum spanning tree,K-ary tree,Spanning tree,Connected dominating set,(a,b)-tree,Shortest-path tree,Kruskal's algorithm,Mathematics,Minimum spanning tree
Journal
Volume
Issue
ISSN
88
4
0020-0190
Citations 
PageRank 
References 
5
0.58
5
Authors
2
Name
Order
Citations
PageRank
Saurabh Srivastava118419.27
R. K. Ghosh213024.60