Abstract | ||
---|---|---|
We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248(n)). This implies that every tree has at most 1.3248(n) minimal 2-dominating sets. We also show that this bound is tight. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1051/ita/2013036 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | Field | DocType |
Domination,2-domination,minimal 2-dominating set,tree,counting,exact exponential algorithm,listing algorithm | Discrete mathematics,Combinatorics,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
47 | 3 | 0988-3754 |
Citations | PageRank | References |
1 | 0.41 | 8 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcin Krzywkowski | 1 | 16 | 6.22 |