Generating all maximal independent sets on trees in lexicographic order
Yizhe Chang, J.S. Wang, R.C.T. Lee · 2003
An algorithm to generate all maximal independent sets in lexicographic order with polynomial time delay between the output of two successive independent sets was proposed by Johnson and Yannakakis (Inform. Process. Let., vol.27, p.119-23, 1988). This algorithm needs exponential amount of space. Johnson suggested an open problem which is to find such an algorithm with polynomial time-delay and space needed between the output of two successive maximal independent sets. The authors investigate this problem on trees. They first introduce a new problem, the constrained maximal independent set problem, which is NP-complete for general graphs. They show that, for trees, the constrained maximal independent set problem can be solved in theta (n) time, where n is the number of vertices. Based upon this algorithm, they propose another algorithm that generates all maximal independent sets in lexicographic order.>