کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428853 686943 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A new self-stabilizing algorithm for maximal p-star decomposition of general graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 11, November 2015, Pages 892–898
نویسندگان
, , ,