Complexity of k-tuple total and total {k}-dominations for some subclasses of bipartite graphs
| Autor: | Valeria Alejandra Leoni, Pablo Daniel Torres, Gabriela R. Argiroffo |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
BIPARTITE GRAPH
021103 operations research Computational complexity theory Matemáticas 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Combinatorics TOTAL {K}-DOMINATION K-TUPLE TOTAL DOMINATION 010201 computation theory & mathematics Signal Processing Bipartite graph COMPUTATIONAL COMPLEXITY Otras Matemáticas Tuple CIENCIAS NATURALES Y EXACTAS Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 138:75-80 |
| ISSN: | 0020-0190 |
| Popis: | We consider two variations of graph total domination, namely, k-tuple total domination and total {k}-domination (for a fixed positive integer k). Their related decision problems are both NP-complete even for bipartite graphs. In this work, we study some subclasses of bipartite graphs. We prove the NP-completeness of both problems (for every fixed k) for bipartite planar graphs and we provide an APX-hardness result for the total domination problem for bipartite subcubic graphs. In addition, we introduce a more general variation of total domination (total (r,m)-domination) that allows us to design a specific linear time algorithm for bipartite distance-hereditary graphs. In particular, it returns a minimum weight total {k}-dominating function for bipartite distance-hereditary graphs. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Torres, Pablo Daniel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas; Argentina |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect