Blocking total dominating sets via edge contractions
| Autor: | Felix Mann, Bernard Ries, Esther Galby |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Computer Science Computational complexity theory Domination analysis Edge (geometry) Graph Blocking (computing) Theoretical Computer Science Combinatorics Edge contraction Focus (optics) Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Theoretical Computer Science. 877:18-35 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2021.03.028 |
| Popis: | In this paper, we study the problem of deciding whether the total domination number of a given graph G can be reduced using exactly one edge contraction (called 1 -Edge Contraction( γ t ) ). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete complexity dichotomy for H-free graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect