Show simple item record

dc.contributor.authorGolovach, Petr
dc.contributor.authorHeggernes, Pinar
dc.contributor.authorKratsch, Dieter
dc.date.accessioned2016-06-10T09:03:29Z
dc.date.available2016-06-10T09:03:29Z
dc.date.issued2015
dc.PublishedLeibniz International Proceedings in Informatics 2015, 43:307-318eng
dc.identifier.urihttps://hdl.handle.net/1956/12088
dc.description.abstractListing, 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.en_US
dc.language.isoengeng
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by/3.0eng
dc.subjectMinimal connected dominating seteng
dc.subjectexact algorithmseng
dc.subjectenumerationeng
dc.titleEnumerating minimal connected dominating sets in graphs of bounded chordalityen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-04-07T06:53:01Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Petr A. Golovach, Pinar Heggernes, and Dieter Kratschen_US
dc.identifier.doihttps://doi.org/10.4230/lipics.ipec.2015.307
dc.identifier.cristin1320310
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution CC BY 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY 3.0