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

Publikationstyp
Conference Paper
Date Issued
2013
Sprache
English
Author(s)
Neggazi, Brahim  
Turau, Volker  
Haddad, Mohammed  
Kheddouci, Hamamache  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/5983
Start Page
74
End Page
85
Citation
Stabilization, safety, and security of distributed systems : 15th international symposium, SSS 2013, Osaka, Japan, November 13 - 16, 2013 ; proceedings / Teruo Higashino... (eds.). - Cham : Springer, 2013. - (8255 LNCS). - Seite 74-85
Contribution to Conference
15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), Osaka, Japan, November 13 - 16, 2013  
Publisher DOI
10.1007/978-3-319-03089-0_6
Scopus ID
2-s2.0-84893979220
Publisher
Springer
A p-star is a complete bipartite graph K1,p with one center node and p leaf nodes. In this paper 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 2[n/p+1] + 2 rounds.
Subjects
Generalized matching
Graph decomposition
Master-slave model
Self-stabilizing algorithm
Stars
DDC Class
004: Informatik