sobre encontrar dos posets que cubren órdenes lineales dadas
Autores: Ordanel, Ivy; Fernandez, Proceso; Adorna, Henry
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
sobre encontrar dos posets que cubren órdenes lineales dadas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Poset
Problema de cobertura
órdenes lineales
Minería de datos
Redes dirigidas
Modelos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 30
Citaciones: Sin citaciones
El Problema de la Cubierta de Poset es un problema de optimización donde el objetivo es determinar un conjunto mínimo de posets que cubra un conjunto dado de órdenes lineales. Este problema es relevante en el campo de la minería de datos, específicamente en la determinación de redes dirigidas o modelos que explican el ordenamiento de objetos en un gran conjunto de datos secuenciales. Ya se sabe que la versión de decisión del problema es NP-Difícil, mientras que su variación donde el objetivo es determinar solo un poset que cubra la entrada está en P. En este estudio, investigamos la variación, que llamamos el Problema de la Cubierta de 2-Poset, donde el objetivo es determinar dos posets, si existen, que cubran las órdenes lineales dadas. Derivamos propiedades sobre posets, lo que conduce a una solución exacta para el Problema de la Cubierta de 2-Poset. Aunque el algoritmo se ejecuta en tiempo exponencial, sigue siendo significativamente más rápido que una solución de fuerza bruta. Además, demostramos que cuando los posets considerados son posets de árbol, el tiempo de ejecución del algoritmo se vuelve polinómico, lo que demuestra que la variación más restringida, que llamamos el Problema de la Cubierta de 2-Árbol-Poset, también está en P.
Descripción
El Problema de la Cubierta de Poset es un problema de optimización donde el objetivo es determinar un conjunto mínimo de posets que cubra un conjunto dado de órdenes lineales. Este problema es relevante en el campo de la minería de datos, específicamente en la determinación de redes dirigidas o modelos que explican el ordenamiento de objetos en un gran conjunto de datos secuenciales. Ya se sabe que la versión de decisión del problema es NP-Difícil, mientras que su variación donde el objetivo es determinar solo un poset que cubra la entrada está en P. En este estudio, investigamos la variación, que llamamos el Problema de la Cubierta de 2-Poset, donde el objetivo es determinar dos posets, si existen, que cubran las órdenes lineales dadas. Derivamos propiedades sobre posets, lo que conduce a una solución exacta para el Problema de la Cubierta de 2-Poset. Aunque el algoritmo se ejecuta en tiempo exponencial, sigue siendo significativamente más rápido que una solución de fuerza bruta. Además, demostramos que cuando los posets considerados son posets de árbol, el tiempo de ejecución del algoritmo se vuelve polinómico, lo que demuestra que la variación más restringida, que llamamos el Problema de la Cubierta de 2-Árbol-Poset, también está en P.