Enumeration of minimal connected dominating sets for chordal graphs

摘要

Enumerating objects of specified type is one of the principal tasks in algorithms. In graph algorithms an often studied task is the enumeration of vertex subsets of the input graph satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input chordal graph. We establish an enumeration algorithm running in time O(1.4736(n)) improving upon a previous O(1.7159(n)) algorithm (Golovach et al., 2016). This is used to show that every n-vertex chordal graph has at most 1.4736(n) minimal connected dominating sets. (C) 2019 Elsevier B.V. All rights reserved.