logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro