logo móvil
Contáctanos

sobre encontrar dos posets que cubren órdenes lineales dadas

Autores: Ordanel, Ivy; Fernandez, Proceso; Adorna, Henry

Idioma: Inglés

Editor: MDPI

Año: 2019

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro