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
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
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.
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.