Skoči na glavni sadržaj

Izvorni znanstveni članak

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


Puni tekst: engleski pdf 246 Kb

str. 67-86

preuzimanja: 347

citiraj


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: 733 *