logo móvil

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

Descargar PDF

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


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.

Documentos Relacionados

Temas Virtualpro