Indice
10 relazioni: Colorazione dei grafi, Cricca (teoria dei grafi), Problema della cricca, Problema dello zaino, Problema di copertura dei vertici, Problema di copertura delle cricche, Richard Karp, Soddisfacibilità booleana, Taglio (teoria dei grafi), Taglio massimo.
Colorazione dei grafi
Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di etichettamento dei grafi; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli.
Vedere 21 problemi NP-completi di Karp e Colorazione dei grafi
Cricca (teoria dei grafi)
In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega.
Vedere 21 problemi NP-completi di Karp e Cricca (teoria dei grafi)
Problema della cricca
In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.
Vedere 21 problemi NP-completi di Karp e Problema della cricca
Problema dello zaino
Il problema dello zaino, o, è un problema di ottimizzazione combinatoria posto nel modo seguente.
Vedere 21 problemi NP-completi di Karp e Problema dello zaino
Problema di copertura dei vertici
Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei più difficili problemi risolvibili non-deterministicamente in tempo polinomiale, assieme al problema del commesso viaggiatore, il knapsack problem, ecc.
Vedere 21 problemi NP-completi di Karp e Problema di copertura dei vertici
Problema di copertura delle cricche
Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP-completo di teoria dei grafi. Il problema era uno dei 21 problemi originali di Richard Karp che erano stati dimostrati NP-completi nel suo saggio del 1972 Riducibilità tra problemi combinatori (Reducibility among Combinatorial Problems).
Vedere 21 problemi NP-completi di Karp e Problema di copertura delle cricche
Richard Karp
Nel 1972 ha pubblicato un elenco di 21 problemi NP-completi. Ha vinto il Premio Turing nel 1985 ed il Premio Kyōto per la tecnologia nel 2008.
Vedere 21 problemi NP-completi di Karp e Richard Karp
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Vedere 21 problemi NP-completi di Karp e Soddisfacibilità booleana
Taglio (teoria dei grafi)
Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti. Ogni taglio determina un insieme di taglio (o cut-set), definito come l'insieme degli archi che hanno i propri estremi nei due sottinsiemi della partizione.
Vedere 21 problemi NP-completi di Karp e Taglio (teoria dei grafi)
Taglio massimo
In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut.