Enumeration and maximum number of maximal irredundant sets for chordal graphs

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of an -vertex chordal graph is at most , and these can be enumerated in time . For interval graphs, we achieve the better upper bound of for the number of maximal irredundant sets and we show that they can be enumerated in time . Finally, we show that an -vertex forest has at most maximal irredundant sets that can be enumerated in time . We complement the latter result by providing a family of forests having at least maximal irredundant sets.