A new self-stabilizing algorithm for maximal p-star decomposition of general graphs

• We address the decomposition of graphs into stars in a distributed way.
• We propose a new self-stabilizing algorithm for decomposing arbitrary graphs into stars having same size.
• The proposed algorithm has polynomial moves complexity.
• Formal proofs for correctness and convergence are provided.

A p  -star is a complete bipartite graph K1,pK1,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⩾1p⩾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(Δ2m)O(Δ2m) moves where m is the number of edges and Δ is maximum node degree in the graph G.