Competitive self-stabilizing \(k\)-clustering

DOI10.1016/j.tcs.2016.02.010zbMath1336.68195OpenAlexW2283454896MaRDI QIDQ264580

Yvan Rivierre, Stéphane Devismes, Karel Heurtefeux, Ajoy K. Datta, Lawrence L. Larmore

Publication date: 31 March 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.010

zbMATH Keywords

self-stabilizationcompetitiveness\(\mathcal{P}\)-completeness\(k\)-clusteringmaximal independent setMIS tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (7)

A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem ⋮ Self-stabilizing algorithms for minimal global powerful alliance sets in graphs ⋮ Squeezing streams and composition of self-stabilizing algorithms ⋮ Self-stabilizing silent disjunction in an anonymous network ⋮ Distance Domination in Graphs ⋮ A Framework for Certified Self-Stabilization ⋮ Optimized silent self-stabilizing scheme for tree-based constructions

Cites Work

• Unnamed Item
• Unnamed Item
• An \(O(n)\)-time self-stabilizing leader election algorithm
• A self-stabilizing \(k\)-clustering algorithm for weighted graphs
• A self-stabilizing algorithm for constructing breadth-first trees
• A taxonomy of problems with fast parallel algorithms
• Self-stabilizing systems in spite of distributed control
• A Packing Inequality for Compact Convex Subsets of the Plane

This page was built for publication: Competitive self-stabilizing \(k\)-clustering