Parámetro de enumeración para problemas de modificación
Autores: Creignou, Nadia; Ktari, Raïda; Meier, Arne; Müller, Julian-Steffen; Olive, Frédéric; Vollmer, Heribert
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Parámetro de enumeración para problemas de modificación
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Teoría de la complejidad parametrizada
Problemas de enumeración
Enumeración ordenada
Estrategias algorítmicas genéricas
Retraso FPT
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
Recientemente, Creignou et al. (Theory Comput. Syst. 2017), introdujeron la clase DelayFPT en la teoría de complejidad parametrizada para capturar la noción de problemas de enumeración parametrizados resolubles de manera eficiente. En este documento, proponemos un marco para la enumeración ordenada parametrizada y mostraremos cómo obtener algoritmos de enumeración con un retraso FPT en el contexto de problemas de modificación generales. Estudiamos estos problemas considerando dos órdenes diferentes de soluciones, a saber, orden lexicográfico y orden por tamaño. Además, presentamos dos estrategias algorítmicas genéricas. La primera se basa en el conocido principio de auto-reducibilidad y se utiliza en el contexto de orden lexicográfico. La segunda muestra que la existencia de una estructura de vecindario entre las soluciones implica la existencia de un algoritmo que se ejecuta con un retraso FPT que produce todas las soluciones ordenadas de forma no decreciente por su tamaño.
Descripción
Recientemente, Creignou et al. (Theory Comput. Syst. 2017), introdujeron la clase DelayFPT en la teoría de complejidad parametrizada para capturar la noción de problemas de enumeración parametrizados resolubles de manera eficiente. En este documento, proponemos un marco para la enumeración ordenada parametrizada y mostraremos cómo obtener algoritmos de enumeración con un retraso FPT en el contexto de problemas de modificación generales. Estudiamos estos problemas considerando dos órdenes diferentes de soluciones, a saber, orden lexicográfico y orden por tamaño. Además, presentamos dos estrategias algorítmicas genéricas. La primera se basa en el conocido principio de auto-reducibilidad y se utiliza en el contexto de orden lexicográfico. La segunda muestra que la existencia de una estructura de vecindario entre las soluciones implica la existencia de un algoritmo que se ejecuta con un retraso FPT que produce todas las soluciones ordenadas de forma no decreciente por su tamaño.