logo móvil
Contáctanos

El problema de la partición domática en grafos separables

Autores: Landete, Mercedes; Sainz-Pardo, José Luis

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

Acceso abierto

Artículo científico
2022

El problema de la partición domática en grafos separables


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Particionamiento
Gráfico
Domático
Algoritmo
Complejidad computacional
NP-completo

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 34

Citaciones: Sin citaciones


Descripción
El problema de partición domática consiste en dividir un grafo dado en un número máximo de conjuntos dominantes disjuntos. Este problema está relacionado con el problema del número domático, que consiste en cuantificar este número máximo de conjuntos dominantes disjuntos. Ambos problemas se demostraron ser NP-completos. En este documento, presentamos un algoritmo de descomposición para encontrar una partición domática en grafos separables, es decir, en grafos con bloques, y como consecuencia, su número domático, reduciendo significativamente la complejidad computacional. Los resultados computacionales ilustran los beneficios del algoritmo de descomposición de bloques.

Otros recursos que podrían interesarte

Temas Virtualpro