Enumerating minimal dominating sets in chordal graphs

LAUR Repository

Show simple item record

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

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account