Aspectos algorítmicos de algunas variaciones de transversales de cliques e conjuntos independientes de cliques en grafos
Autores: Lee, Chuan-Min
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
Categoría
Ingeniería y Tecnología
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 15
Citaciones: Sin citaciones
Este documento estudia el problema de independencia de la máxima clique y algunas variaciones del problema de transversal de cliques como el problema de la -clique, máxima clique, clique negativa, clique firmada y problemas de transversal de clique -fold desde aspectos algorítmicos para -árboles, soles, gráficos planares, gráficos doblemente cordales, gráficos perfectos de cliques, gráficos totales, gráficos divididos, gráficos de líneas y gráficos doblemente cordales. Damos ecuaciones para calcular los números de transversal de clique -clique, clique negativa, clique firmada y -fold para soles, y mostramos que el problema de transversal de clique -clique es solucionable en tiempo polinómico para gráficos cuyos números de transversal de clique son iguales a sus números de independencia de clique. También mostramos la relación entre los problemas de cliques firmadas y de generalización y presentamos resultados de NP-completitud para los problemas considerados en -árboles con no acotado, gráficos planares, gráficos doblemente cordales, gráficos totales, gráficos divididos, gráficos de líneas y gráficos doblemente cordales.
Descripción
Este documento estudia el problema de independencia de la máxima clique y algunas variaciones del problema de transversal de cliques como el problema de la -clique, máxima clique, clique negativa, clique firmada y problemas de transversal de clique -fold desde aspectos algorítmicos para -árboles, soles, gráficos planares, gráficos doblemente cordales, gráficos perfectos de cliques, gráficos totales, gráficos divididos, gráficos de líneas y gráficos doblemente cordales. Damos ecuaciones para calcular los números de transversal de clique -clique, clique negativa, clique firmada y -fold para soles, y mostramos que el problema de transversal de clique -clique es solucionable en tiempo polinómico para gráficos cuyos números de transversal de clique son iguales a sus números de independencia de clique. También mostramos la relación entre los problemas de cliques firmadas y de generalización y presentamos resultados de NP-completitud para los problemas considerados en -árboles con no acotado, gráficos planares, gráficos doblemente cordales, gráficos totales, gráficos divididos, gráficos de líneas y gráficos doblemente cordales.