Problema di copertura dei vertici
Da Wikipedia, l'enciclopedia libera.
Il problema di copertura dei vertici, detto anche vertex cover, appartiene alla classe di equivalenza dei problemi completi non deterministici, assieme al problema del commesso viaggiatore, il knapsack problem, etc.
Questa classe di problemi è detta NP-completo, si dice cioè che il vertex cover o problema di copertura dei vertici è un problema NP-completo. È utile a riguardo la dimostrazione di equivalenza fra tutti i problemi NP-completo, come premesso. Mediante questi problemi si ottengono, ad esempio, modelli per la logistica o per il calcolo delle spese nella produzione. Il problema complementare al vertex-cover è detto edge cover.
