Extending the Max Algorithm for maximum independent set
Christoph Brause, Ngoc Chi Lê, Ingo Schiermeyer · Discussiones Mathematicae Graph Theory · 2015
The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.