Name
Abstract | ||
|---|---|---|
Enumerating objects of specified type is one of the principal tasks in algorithms. In graph algorithms an often studied task is the enumeration of vertex subsets of the input graph satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input chordal graph. We establish an enumeration algorithm running in time O(1.4736n) improving upon a previous O(1.7159n) algorithm (Golovach et al., 2016) . This is used to show that every n-vertex chordal graph has at most 1.4736n minimal connected dominating sets. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2019.07.015 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Enumeration,Minimal connected dominating sets,Chordal graphs | Journal | 278 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Dieter Kratsch | 3 | 1957 | 146.89 |
| Reza Saei | 4 | 24 | 3.62 |