logo móvil
Contáctanos

expansión lemma-variaciones y aplicaciones a preprocesamiento de tiempo polinómico

Autores: Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh

Idioma: Inglés

Editor: MDPI

Año: 2023

Descargar PDF

Acceso abierto

Artículo científico
2023

expansión lemma-variaciones y aplicaciones a preprocesamiento de tiempo polinómico


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Núcleo
Tratable de parámetro fijo
Lema de expansión
De tamaño polinomial
Límites inferiores
óptimo asintóticamente

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 41

Citaciones: Sin citaciones


Descripción
En la complejidad parametrizada, es bien conocido que un problema parametrizado es tratable por parámetro fijo si y solo si tiene un núcleo: una instancia equivalente a la instancia de entrada, cuyo tamaño es solo una función del parámetro. El tamaño del núcleo puede ser exponencial o peor, lo que resulta en una búsqueda de problemas tratables por parámetro fijo con núcleos de tamaño polinomial. Los avances en maquinaria (mostrando límites inferiores para los tamaños de los núcleos) han llevado a los investigadores a cuestionar cuáles son los tamaños óptimos asintóticamente para los núcleos de problemas tratables por parámetro fijo. En este artículo, hicimos un estudio de una herramienta llamada lema de expansión que ayuda a reducir el tamaño del núcleo. Su origen temprano fue en forma de descomposición de coronas, es decir, para obtener el núcleo lineal del problema; el lema específico fue identificado como la herramienta detrás del núcleo óptimo para el problema del conjunto de vértices de retroalimentación no dirigida. Desde entonces, se han descubierto varias variaciones y extensiones de la herramienta. Las estudiamos junto con sus aplicaciones en este artículo.

Otros recursos que podrían interesarte

Temas Virtualpro