An efficient algorithm to generate all maximal independent sets on trapezoid graphs
Marinmoy Hota, Madhumangal Pal, Tapan K. Pal · International Journal of Computer Mathematics · 1999
Generation of all maximal independent sets (MIS) is a NP-complete problem for general graphs. In this paper, using a particular geometric property of trapezoid graph, an efficient algorithm is designed which enables to generate all maximal independent sets for a trapezoid graph in time, where [mbar] and a are respectively the number of edges of the complement graph of the given graph and the number of generated maximal independent sets. There is no prior algorithm available to solve this problem of finding all MIS for trapezoid graphs.