Skip to the main content

Original scientific paper

Independent sets and vertex covers considered within the context of robust optimization

Ana Klobučar ; University of Zagreb, Faculty of Mechanical Engineering and Naval Architecture, Zagreb, Croatia
Robert Manger ; University of Zagreb, Faculty of Science, Department of Mathematics, Zagreb, Croatia


Full text: english pdf 246 Kb

page 67-86

downloads: 520

cite


Abstract

This paper studies robust variants of the maximum weighted independent set problem and the minimum weighted vertex cover problem, respectively. Both problems are posed in a vertex-weighted graph. The paper explores whether the complement of a robustly optimal independent set must be a robustly optimal vertex cover, and vice-versa.

Keywords

weighted graph; independent set; vertex cover; robust optimization

Hrčak ID:

235541

URI

https://hrcak.srce.hr/235541

Publication date:

12.3.2020.

Visits: 1.235 *