Explorando problemas de clique transversal para grafos -degenerados con fijo: de solubilidad en tiempo polinómico a complejidad parametrizada
Autores: Lee, Chuan-Min
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Explorando problemas de clique transversal para grafos -degenerados con fijo: de solubilidad en tiempo polinómico a complejidad parametrizada
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Problemas de clique transversal
Grafos degenerados
Complejidades computacionales
Solucionables en tiempo polinómico
NP-completitud
Complejidad parametrizada
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Este documento explora los desafíos computacionales de los problemas de transversal de cliques en grafos -degenerados, que son comúnmente encontrados en la ciencia computacional teórica y diversas aplicaciones de redes. Examinamos los grafos -degenerados para resaltar su utilidad en la representación de estructuras dispersas y evaluamos varias variaciones de problemas de transversal de cliques, incluyendo los problemas de transversal de cliques de -veces y de -cliques, centrándonos en sus complejidades computacionales para diferentes categorías de grafos. Nuestro análisis identifica que ciertas instancias de estos problemas son resolubles en tiempo polinómico en clases específicas de grafos, como grafos 1-degenerados o 2-degenerados. Sin embargo, para grafos -degenerados donde , estos problemas generalmente escalan a NP-completitud. También exploramos la complejidad parametrizada, señalando condiciones específicas que hacen que estos problemas sean tratables mediante parámetros fijos.
Descripción
Este documento explora los desafíos computacionales de los problemas de transversal de cliques en grafos -degenerados, que son comúnmente encontrados en la ciencia computacional teórica y diversas aplicaciones de redes. Examinamos los grafos -degenerados para resaltar su utilidad en la representación de estructuras dispersas y evaluamos varias variaciones de problemas de transversal de cliques, incluyendo los problemas de transversal de cliques de -veces y de -cliques, centrándonos en sus complejidades computacionales para diferentes categorías de grafos. Nuestro análisis identifica que ciertas instancias de estos problemas son resolubles en tiempo polinómico en clases específicas de grafos, como grafos 1-degenerados o 2-degenerados. Sin embargo, para grafos -degenerados donde , estos problemas generalmente escalan a NP-completitud. También exploramos la complejidad parametrizada, señalando condiciones específicas que hacen que estos problemas sean tratables mediante parámetros fijos.