An anonymous self-stabilizing algorithm for 1-maximal independent set in trees

DOI10.1016/J.IPL.2004.03.010MaRDI QIDQ2390286zbMATH OpenOpenAlexFDO

Authors Zhengnan Shi, Stephen T. Hedetniemi, Wayne Goddard

Publication date 21 July 2009

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

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

zbMATH Keywords

distributed computingfault tolerancegraph algorithmsmaximal independent set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks
• An efficient silent self-stabilizing 1-maximal matching algorithm in anonymous networks
• A self-stabilizing algorithm for maximal matching in anonymous networks
• MIS on trees
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets

Cites work

• A self-stabilizing algorithm for maximal matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• scientific article; zbMATH DE number 4105008 (Why is no real title available?)
• Introduction to Distributed Algorithms
• On generalised minimal domination parameters for paths
• Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
• Self-stabilization
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• Self-stabilizing systems in spite of distributed control
• The local nature of \(\Delta\)-coloring and its algorithmic applications

Cited in

(14)

• A self-stabilizing enumeration algorithm.
• scientific article; zbMATH DE number 2086249 (Why is no real title available?)
• Efficient self-stabilizing algorithm for independent strong dominating sets in arbitrary graphs
• A self-stabilizing algorithm to maximal 2-packing with improved complexity
• A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler
• SELF-STABILIZING ANONYMOUS LEADER ELECTION IN A TREE
• Maximum matching for anonymous trees with constant space per process
• Anonymous Daemon Conversion in Self-stabilizing Algorithms by Randomization in Constant Space
• A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph
• A fault-containing self-stabilizing \((3-\frac 2{\varDelta+1})\)-approximation algorithm for vertex cover in anonymous networks
• Self-stabilizing 2-minimal dominating set algorithms based on loop composition
• A self-stabilizing 1-maximal independent set algorithm
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• A self-stabilizing 23-approximation algorithm for the maximum matching problem

This page was built for publication: An anonymous self-stabilizing algorithm for 1-maximal independent set in trees

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