Self-stabilizing algorithms for minimal dominating sets and maximal independent sets

In the self-stabilizing algorithmic paradigm for distributed computation, each node has only a local view of the system, yet in a finite amount of time, the system converges to a global state satisfying some desired property. In this paper, we present polynomial time self-stabilizing algorithms for...

Full description

Saved in:
Bibliographic Details
Published in:Computers & mathematics with applications (1987) 2003-09, Vol.46 (5), p.805-811
Main Authors: Hedetniemi, S.M., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.
Format: Article
Language:English
Subjects:
Dominating set
Graph
Independent set
Self-stabilizing algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the self-stabilizing algorithmic paradigm for distributed computation, each node has only a local view of the system, yet in a finite amount of time, the system converges to a global state satisfying some desired property. In this paper, we present polynomial time self-stabilizing algorithms for finding a dominating bipartition, a maximal independent set, and a minimal dominating set in any graph.
ISSN:0898-1221
1873-7668
DOI:10.1016/S0898-1221(03)90143-X