Home
This program is an implementation of Luby's algorithm, which finds a maximal independent set distributedly. The program is written by Hasan Heydari with c++ language and MPICH library. In what follows, the definition of the problem of maximal independent set and Luby's algorithm are presented. For more information about the program, see the following pages:
Given an undirected graph G= (V, E), an independent set in G is a subset of vertices U ⊆ V, such that no two vertices in U are adjacent. An independent set U is called MIS if no further vertex can be added to U without violating independence condition.
An Example
Consider the following graph. This graph has some independent set and some maximal independent set. In what follows, three of its independent sets and three of its maximal independent sets are shown.
In each of the following graphs, the orange vertices are members of an independent set.
In each of the following graphs, the orange vertices are members of a maximal independent set.
The following algorithm is Luby's algorithm. It is a randomized distributed algorithm, which finds a maximal independent set in O(log n) rounds with high probability (n is the number of nodes). Indeed, in each node, the while loop of the following algorithm terminates in O(log n) rounds with high probability.
