✦ LIBER ✦

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

✍ Scribed by S.M. Hedetniemi; S.T. Hedetniemi; D.P. Jacobs; P.K. Srimani

Book ID: 108458508
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 551 KB
Volume: 46
Category: Article
ISSN: 0898-1221
DOI: 10.1016/s0898-1221(03)90143-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An anonymous self-stabilizing algorithm

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

✍ Zhengnan Shi; Wayne Goddard; Stephen T. Hedetniemi 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Maximally independent sets, minimal gene

Maximally independent sets, minimal generating sets, and irreducibles

✍ Bernard P. Zeigler 📂 Article 📅 1974 🏛 Springer 🌐 English ⚖ 364 KB

Parallel algorithms for fractional and m

Parallel algorithms for fractional and maximal independent sets in planar graphs

✍ N. Dadoun; D.G. Kirkpatrick 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 947 KB

Efficient Exact Algorithms through Enume

Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques

✍ Venkatesh Raman; Saket Saurabh; Somnath Sikdar 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 266 KB

A self-stabilizing algorithm for finding

A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model

✍ Tetz C. Huang; Ji-Cherng Lin; Chih-Yuan Chen; Cheng-Pin Wang 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 202 KB

A 2-dominating set in a distributed system is a set of processors such that each processor outside the set has at least two neighbors in the set. In applications, a 2-dominating set can be considered as an ideal place in the system for allocating resources, and a minimal 2-dominating set allows for

Fast RNC and NC algorithms for maximal p

Fast RNC and NC algorithms for maximal path sets

✍ Ryuhei Uehara; Zhi-Zhong Chen; Xin He 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 659 KB

We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(logn) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log' n) time with 0(&n + m)/ log n) processors on an EREW PRAM. The