Blocking Total Dominating Sets Via Edge Contractions
- Galby, Esther University of Fribourg
- Mann, Felix University of Fribourg
- Ries, Bernard University of Fribourg
- 26.03.2021
Published in:
- Theoretical Computer Science. - Elsevier. - 2021, vol. 877, p. 18-35
English
In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
-
License undefined
- Identifiers
-
- RERO DOC 333240
- DOI 10.1016/j.tcs.2021.03.028
- Persistent URL
- https://folia.unifr.ch/unifr/documents/309575
Export to…
Statistics
Document views: 206
File downloads:
- Document: 425