Izvorni znanstveni članak

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

Ana Klobučar orcid.org/0000-0002-0260-5439 ; University of Zagreb, Faculty of Mechanical Engineering and Naval Architecture, Zagreb, Croatia
Robert Manger orcid.org/0000-0003-0953-6517 ; University of Zagreb, Faculty of Science, Department of Mathematics, Zagreb, Croatia

Sažetak

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.

Ključne riječi

weighted graph; independent set; vertex cover; robust optimization

Hrčak ID:

235541

URI

https://hrcak.srce.hr/235541

Datum izdavanja:

12.3.2020.

Posjeta: 1.428 *