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

DOI10.1016/J.IPL.2015.05.010MaRDI QIDQ2353636zbMATH OpenOpenAlexFDO

Authors Brahim Neggazi, Mohammed Haddad, H. Kheddouci

Publication date 15 July 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2015.05.010

zbMATH Keywords

graph algorithmsdistributed systemsfault tolerancegraph decompositionself-stabilizationgeneralized matchinguniform stars

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Graph designs and isomorphic decomposition (05C51)

Recommendations

• A \(O(m)\) self-stabilizing algorithm for maximal triangle partition of general graphs
• Self-stabilizing deterministic network decomposition
• scientific article; zbMATH DE number 2114409
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
• A self-stabilizing algorithm to maximal 2-packing with improved complexity

Cites work

• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon
• A self-stabilizing algorithm for coloring planar graphs
• A self-stabilizing algorithm for maximal matching
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• Balanced graph partitioning
• Balanced star decompositions of regular multigraphs and \(\lambda\)-fold complete bipartite graphs
• Decomposition of complete graphs into stars
• Fast self-stabilizing minimum spanning tree construction. Using compact nearest common ancestor labeling scheme
• Linear star decomposition of lobster
• Linear time self-stabilizing colorings
• Maximal matching stabilizes in time \(O(m)\)
• On the Complexity of General Graph Factor Problems
• On the completeness of a generalized matching problem
• Robust self-stabilizing weight-based clustering algorithm
• Self-stabilization
• Self-stabilizing deterministic network decomposition
• Self-stabilizing systems in spite of distributed control
• Star factorizations of graph products

Cited in

(4)

• scientific article; zbMATH DE number 5237247 (Why is no real title available?)
• Self-stabilizing deterministic network decomposition
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• A log-star distributed maximal independent set algorithm for growth-bounded graphs

This page was built for publication: A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353636)