Generate all maximal independent sets in permutation graphs

Abstract

In this paper, an O(n log n + k) time algorithm is presented to generate all maximal independent sets in a permutation graph, where n is the number of vertices in the graph and k is the number of vertices generated. The space requirement is O(n log n).

Keywords:

• Data structures
• design of algorithms
• maximal independent sets
• permutation graphs

C.R.Categories:

• G2.2