An efficient algorithm to generate all maximal independent sets on trapezoid graphs

Abstract

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.

Keywords:

• Design and analysis of algorithms
• data structure
• independent sets
• trapezoid graph
• tree

C.R. Categories:

• E1
• F2
• G.2.2
• I.1.2