Enumerating minimal dominating sets in chordal graphs

Abu-Khzam, Faisal N.; Heggernes, Pinar

dc.contributor.author	Abu-Khzam, Faisal N.
dc.contributor.author	Heggernes, Pinar
dc.date.accessioned	2016-11-08T14:05:49Z
dc.date.available	2016-11-08T14:05:49Z
dc.date.copyright	2016	en_US
dc.date.issued	2016-11-08
dc.identifier.issn	0020-0190	en_US
dc.identifier.uri	http://hdl.handle.net/10725/4760
dc.description.abstract	The maximum number of minimal dominating sets in a chordal graph on n vertices is known to be at most 1.6181n. However, no example of a chordal graph with more than 1.4422n minimal dominating sets is known. In this paper, we narrow this gap between the known upper and lower bounds by showing that the maximum number of minimal dominating sets in a chordal graph is at most 1.5214n.	en_US
dc.language.iso	en	en_US
dc.title	Enumerating minimal dominating sets in chordal graphs	en_US
dc.type	Article	en_US
dc.description.version	Published	en_US
dc.author.school	SAS	en_US
dc.author.idnumber	200302941	en_US
dc.author.department	Computer Science and Mathematics	en_US
dc.description.embargo	N/A	en_US
dc.relation.journal	Information Processing Letters	en_US
dc.journal.volume	116	en_US
dc.journal.issue	12	en_US
dc.article.pages	739-743	en_US
dc.keywords	Input sensitive enumeration	en_US
dc.keywords	Branching algorithm	en_US
dc.keywords	Maximum number of minimal dominating sets	en_US
dc.keywords	Chordal graphs	en_US
dc.keywords	Graph algorithms	en_US
dc.identifier.doi	http://dx.doi.org/10.1016/j.ipl.2016.07.002	en_US
dc.identifier.ctation	Abu-Khzam, F. N., & Heggernes, P. (2016). Enumerating minimal dominating sets in chordal graphs. Information Processing Letters, 116(12), 739-743.	en_US
dc.author.email	faisal.abukhzam@lau.edu.lb	en_US
dc.identifier.tou	http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php	en_US
dc.identifier.url	http://www.sciencedirect.com/science/article/pii/S0020019016301004	en_US
dc.orcid.id	https://orcid.org/0000-0001-5221-8421