License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.307
URN: urn:nbn:de:0030-drops-55925
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5592/
Go to the corresponding LIPIcs Volume Portal

Golovach, Petr A. ; Heggernes, Pinar ; Kratsch, Dieter

Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality

pdf-format:
29.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{golovach_et_al:LIPIcs:2015:5592,
  author =	{Petr A. Golovach and Pinar Heggernes and Dieter Kratsch},
  title =	{{Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{307--318},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5592},
  URN =		{urn:nbn:de:0030-drops-55925},
  doi =		{10.4230/LIPIcs.IPEC.2015.307},
  annote =	{Keywords: Minimal connected dominating set, exact algorithms, enumeration}
}

Keywords: Minimal connected dominating set, exact algorithms, enumeration
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI