A Self-Stabilizing Algorithm for Maximal p-Star Decomposition of General Graphs (B. Neggazi, V. Turau, M. Haddad, H. Kheddouci)
Abstract
A p-star is a complete bipartite graph K1,p with one center node and p leaf nodes. In this work we propose the first distributed self- stabilizing algorithm for graph decomposition into p-stars. For a graph G and an integer p ≥ 1, this decomposition provides disjoint components of G where each component forms a p-star. We prove convergence and correctness of the algorithm under an unfair distributed daemon. The stabilization time is O(n) rounds.
A short bio
Since september 2011, Brahim Neggazi is a Ph.D. student in LIRIS Laboratory within GrAMA team. He is supervised by Pr. Hamamache Kheddouci and Dr. Mohammed Haddad. His research interests focus on graph decompositions and search for specific patterns in graphs using self-stabilizing and distributed algorithms.
