MIS algorithms visualisation

This application is intended to visualise algorithms finding Maximal Indepenent Set. There are two implementations: Simple and Randomized.

Simple Naive algorithm

This algorithms tries puts a node to the result iff any node from his neighbour is not already in result. Complexity is obviously linear.

Randomized Parallel algorithm

Second algorithm is randomized algorithm that puts to the result with higher probability nodes that have smallest degree. In second phase original graph is modified and nodes that are already part of the result are removed along with their neighbourhood. This algorithm has complexity of O(log n) and can be executed in parallel (with some synchronization between phases).