Algorithms for maximal independent set problems

This study involves the development of Maximal Independent Set (MIS) for an arbitrary input graph G. Here we investigate the polynomial-time algorithm using various techniques like greedy, random, divide and conquer and dynamic programming for maximal independent set of a simple graph. An algorithm is be considered ‘efficient’ if its running time is polynomial: O(n^c ) for some constant c, where n is the size of the input. The computation of a maximal independent set of minimum size is NP-hard for general graphs.