Enumeration of minimal connected dominating sets for chordal graphs
| Autor: | Reza Saei, Pinar Heggernes, Dieter Kratsch, Petr A. Golovach |
|---|---|
| Přispěvatelé: | Laboratoire de Génie Informatique, de Production et de Maintenance (LGIPM), Université de Lorraine (UL) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Vertex (graph theory)
Mathematics::Combinatorics Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning Enumeration algorithm 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph [SPI.AUTO]Engineering Sciences [physics]/Automatic Combinatorics 010201 computation theory & mathematics Chordal graph Enumeration Discrete Mathematics and Combinatorics Graph algorithms ComputingMilieux_MISCELLANEOUS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, Elsevier, 2020, 278, pp.3-11. ⟨10.1016/j.dam.2019.07.015⟩ |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.07.015⟩ |
| Popis: | 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 . 473 6 n ) improving upon a previous O ( 1 . 715 9 n ) algorithm (Golovach et al., 2016) . This is used to show that every n -vertex chordal graph has at most 1 . 473 6 n minimal connected dominating sets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect