TY - JOUR
T1 - Enumerating minimal dominating sets in chordal graphs
AU - Abu-Khzam, Faisal N.
AU - Heggernes, Pinar
PY - 2016/12/1
Y1 - 2016/12/1
N2 - 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.
AB - 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.
KW - Branching algorithm
KW - Chordal graphs
KW - Graph algorithms
KW - Input sensitive enumeration
KW - Maximum number of minimal dominating sets
UR - http://www.scopus.com/inward/record.url?scp=84989830093&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2016.07.002
DO - 10.1016/j.ipl.2016.07.002
M3 - Article
AN - SCOPUS:84989830093
VL - 116
SP - 739
EP - 743
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
IS - 12
ER -