Artículo

Limited Packing and Multiple Domination problems: Polynomial time reductions

Leoni, Valeria AlejandraIcon ; Nasini, Graciela LeonorIcon
Fecha de publicación: 02/2014
Editorial: Elsevier Science
Revista: Discrete Applied Mathematics
ISSN: 0166-218X
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

The Limited Packing and Multiple Domination problems in graphs have closely-related definitions and the same computational complexity on several graph classes. In this work we present two polynomial time reductions between them. Besides, we take into consideration generalized versions of these problems and obtain polynomial time reductions between each one and its generalized version.
Palabras clave: COMPUTATIONAL COMPLEXITY , K-LIMITED PACKING , K-TUPLE DOMINATING SET , POLYNOMIAL TIME REDUCTIONS
 
Archivos asociados
Thumbnail
 
Tamaño: 389.8Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Atribución-NoComercial-SinDerivadas 2.5 Argentina (CC BY-NC-ND 2.5 AR)
Identificadores
URI: http://hdl.handle.net/11336/21872
DOI: http://dx.doi.org/10.1016/j.dam.2013.10.023
URL: http://www.sciencedirect.com/science/article/pii/S0166218X13004514
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Citación
Leoni, Valeria Alejandra; Nasini, Graciela Leonor; Limited Packing and Multiple Domination problems: Polynomial time reductions; Elsevier Science; Discrete Applied Mathematics; 164; 2; 2-2014; 547-553
Compartir
Altmétricas