Intercettazioni telefoniche

Una agenzia investigativa deve intercettare le comunicazioni di una rete rappresentata da un grafo non orientato $G=(N,A)$. Per fare ciò è necessario installare in alcuni nodi della rete degli apparecchi speciali in grado di intercettare le comunicazioni che avvengono su tutti gli archi incidenti nel nodo in cui è installato un apparecchio. Il costo di installazione di ciascun apparecchio è dato da $c_i, i\in N$. Il problema consiste nel trovare in quale sottoinsieme di nodi installare gli apparecchi in modo che tutti gli archi della rete siano sotto controllo, minimizzando il costo complessivo.

Leggi i suggerimenti <>