Resolviendo variantes robustas del problema del conjunto independiente con peso máximo en árboles
Autores: Klobuar, Ana; Manger, Robert
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Resolviendo variantes robustas del problema del conjunto independiente con peso máximo en árboles
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Conjunto independiente ponderado máximo
Variantes robustas
árboles
NP-duro
Heurística
Algoritmo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 33
Citaciones: Sin citaciones
Este documento trata sobre el problema del conjunto independiente ponderado máximo (MWIS). Consideramos varias variantes robustas del problema MWIS en árboles y demostramos que la mayoría de ellas son NP-difíciles. Proponemos una heurística para resolver las variantes robustas de MWIS consideradas, la cual está personalizada para árboles. Demostramos mediante experimentos que nuestro algoritmo produce soluciones de alta calidad y se ejecuta mucho más rápido que un software de optimización de propósito general.
Descripción
Este documento trata sobre el problema del conjunto independiente ponderado máximo (MWIS). Consideramos varias variantes robustas del problema MWIS en árboles y demostramos que la mayoría de ellas son NP-difíciles. Proponemos una heurística para resolver las variantes robustas de MWIS consideradas, la cual está personalizada para árboles. Demostramos mediante experimentos que nuestro algoritmo produce soluciones de alta calidad y se ejecuta mucho más rápido que un software de optimización de propósito general.