文章基本信息

标题：Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality
本地全文：下载
作者：Petr A. Golovach ; Pinar Heggernes ; Dieter Kratsch 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：43
页码：307-318
DOI：10.4230/LIPIcs.IPEC.2015.307
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input graph from various graph classes of bounded chordality. We establish enumeration algorithms as well as lower and upper bounds for the maximum number of minimal connected dominating sets in such graphs. In particular, we present algorithms to enumerate all minimal connected dominating sets of chordal graphs in time O(1.7159^n), of split graphs in time O(1.3803^n), and of AT-free, strongly chordal, and distance-hereditary graphs in time O^*(3^{n/3}), where n is the number of vertices of the input graph. Our algorithms imply corresponding upper bounds for the number of minimal connected dominating sets for these graph classes.
关键词：Minimal connected dominating set; exact algorithms; enumeration