Vai al contenuto

Problemi di cricca

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

  • Dato un grafo non orientato \(G=(V,E)\), una cricca è un sottoinsieme di vertici a due a due adiacenti; l'obiettivo è massimizzarne la cardinalità \(\omega(G)\), o un peso dei suoi vertici o dei suoi lati.

  • Un insieme stabile di \(G\) è una cricca del grafo complementare \(\bar G\), quindi il problema dell'insieme stabile massimo appartiene alla stessa famiglia.

Problema Sigla Differenza
Problema della cricca massima MCP Il problema centrale della famiglia.
Problema dell'insieme stabile massimo MSSP Un sottoinsieme è una cricca di \(G\) se e solo se è un insieme stabile di \(\overline{G}\): \(\omega(G) = \alpha(\overline{G})\) e \(\alpha(G) = \omega(\overline{G})\).
Problema della cricca massima pesata sui vertici VWMCP Con tutti i pesi \(w_v=1\) è l'MCP.
Problema della cricca massima pesata sui lati EWMCP Con \(r_{uv}=1\) è di nuovo l'MCP, perché \(r(K)=\binom{|K|}{2}\) cresce con \(|K|\).