l'accesso più veloce di browser!
10 relazioni: Colorazione dei grafi, Cricca (teoria dei grafi), Grafo complemento, Insieme indipendente (teoria dei grafi), NP (complessità), NP-completo, P (complessità), Teoria dei grafi, Teoria della complessità computazionale, 21 problemi NP-completi di Karp.
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.
Nuovo!!: Problema di copertura delle cricche e Colorazione dei grafi · Mostra di più »
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.
Nuovo!!: Problema di copertura delle cricche e Cricca (teoria dei grafi) · Mostra di più »
Grafo complemento
Nella teoria dei grafi, il complemento o inverso di un grafo G è un grafo H sugli stessi vertici tale che due distinti vertici di H sono adiacenti se e solo se non sono adiacenti in G. Ossia, per generare il complemento di un grafo, si riempiono tutti gli spigoli mancanti richiesti per formare un grafo completo, e si rimuovono tutti gli spigoli che vi erano in precedenza.
Nuovo!!: Problema di copertura delle cricche e Grafo complemento · Mostra di più »
Insieme indipendente (teoria dei grafi)
Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due.
Nuovo!!: Problema di copertura delle cricche e Insieme indipendente (teoria dei grafi) · Mostra di più »
NP (complessità)
La classe di problemi NP comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale.
Nuovo!!: Problema di copertura delle cricche e NP (complessità) · Mostra di più »
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.
Nuovo!!: Problema di copertura delle cricche e NP-completo · Mostra di più »
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Nuovo!!: Problema di copertura delle cricche e P (complessità) · Mostra di più »
Teoria dei grafi
In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi si occupa di studiare i grafi, che sono oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentirne delle analisi in termini quantitativi e algoritmici.
Nuovo!!: Problema di copertura delle cricche e Teoria dei grafi · Mostra di più »
Teoria della complessità computazionale
In informatica, la teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.
Nuovo!!: Problema di copertura delle cricche e Teoria della complessità computazionale · Mostra di più »
21 problemi NP-completi di Karp
Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi.
Nuovo!!: Problema di copertura delle cricche e 21 problemi NP-completi di Karp · Mostra di più »
