Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees (CROSBI ID 276030)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Klobučar, Ana ; Manger, Robert
engleski
Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees
This paper deals with the maximum weighted independent set (MWIS) problem. We consider several robust variants of the MWIS problem on trees and prove that most of them are NP-hard. We propose a heuristic for solving the considered robust MWIS variants, which is customized for trees. We demonstrate by experiments that our algorithm produces high-quality solutions and runs much faster than a general-purpose optimization software.
weighted graph ; independent set ; robust optimization ; tree ; complexity ; heuristic
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano