Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees

Ana Klobučar and Robert Manger
Additional contact information
Ana Klobučar: Faculty of Mechanical Engineering and Naval Architecture, University of Zagreb, 10000 Zagreb, Croatia
Robert Manger: Department of Mathematics, Faculty of Science, University of Zagreb, 10000 Zagreb, Croatia

Mathematics, 2020, vol. 8, issue 2, 1-16

Abstract: 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.

Keywords: weighted graph; independent set; robust optimization; tree; complexity; heuristic (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/2/285/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/2/285/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:2:p:285-:d:322901

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().