Abstract
A p-star is a complete bipartite graph K-1,K-p with one center node and p leaves. In this paper, we propose a polynomial self-stabilizing algorithm for maximal graph decomposition into p-stars. Given an arbitrary graph G and a positive integer p >= 1, this decomposition provides disjoint components of G, such that each component induces a p-star in G. Under the unfair distributed scheduler, the algorithm converges within O (Delta(2)m) moves where m is the number of edges and Delta is maximum node degree in the graph G. (C) 2015 Elsevier B.V. All rights reserved.