Heuristics & Metaheuristics
for Optimization & Learning

Sviluppo Progetto Minimum Weight Vertex Cover

Esame del 15 Luglio 2026

Problema da Risolvere

The Minimum Weight Vertex Cover (MWVC) problem is a fundamental graph problem in Network Science, with many important real-life applications such as, for example, in wireless communication, circuit design and network flows. Given an undirected graph G = (V, E), and a weight W_i assigned to each vertex i, the MWVC problem asks to find among all subsets S ⊂ V that are vertex covers, a subset S^* for which the sum of the weights of the vertices is minimal.

Report: download

Problem instances: download