Isomorfismo di sottografi

Nella teoria della complessità computazionale, l'isomorfismo di sottografo è un problema decisionale di tipo NP-completo. La descrizione del problema è la seguente: siano dati G1 e G2 due grafi, è G1 isomorfo ad un sottografo di G2? La ricerca del sottografo isomorfo ha applicazioni in chemioinformatica.

Usa IA

Indice

1. 4 relazioni: Algoritmo di Ullmann, Klaus Wagner, NP-completo, Problema della cricca.

Algoritmo di Ullmann

L'algoritmo di Ullmann è un algoritmo per la soluzione del problema dell'isomorfismo di sottografi. Il problema è NP-completo e l'algoritmo non fornisce una soluzione in tempo polinomiale, tuttavia utilizza tecniche quali il backtracking per diminuire il tempo effettivo di esecuzione, che però non hanno effetto sulla complessità asintotica, che rimane esponenziale.

Vedere Isomorfismo di sottografi e Algoritmo di Ullmann

Klaus Wagner

Wagner studiò topologia all'Università di Colonia sotto la direzione di Karl Dorge, che a sua volta era un ex allievo di Issai Schur.

Vedere Isomorfismo di sottografi e Klaus Wagner

NP-completo

Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi risolvibili non-deterministicamente 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.

Vedere Isomorfismo di sottografi e NP-completo

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 Isomorfismo di sottografi e Problema della cricca

Conosciuto come Isomorfismo di sottografo, Subgraph isomorphism problem.

Unionpedia è una mappa concettuale o rete semantica organizzata come un'enciclopedia o un dizionario. Esso fornisce una breve definizione di ogni concetto e le sue relazioni.

Si tratta di una mappa mentale in linea gigante che serve come base per gli schemi concettuali, immagini o sintesi sinaptica. E 'gratuito - liberi, liberi di usare e ogni elemento o documento può essere scaricato. E 'uno strumento, risorsa o di riferimento per lo studio, la ricerca, l'istruzione, la formazione o istruzione che gli insegnanti possono utilizzare, insegnanti, professori, educatori, alunni e studenti; o la scuola per il mondo accademico, a scuola, primaria, secondaria, di mezzo, università, laurea tecnica, college, università, laurea, master o dottorati; per documenti, relazioni, documenti, progetti, idee, documentazione, riassunti, sondaggi o tesi. Ecco la definizione, spiegazione, descrizione, o il significato di ogni significativo su cui avete bisogno di informazioni, e una lista o un elenco di concetti correlati come appare un glossario. Disponibile in italiano, inglese, spagnolo, portoghese, giapponese, cinese, francese, tedesco, polacco, olandese, russo, arabo, hindi, svedese, ucraino, ungherese, catalano, ceco, ebraico, danese, finlandese, indonesiano, norvegese, rumeno, turco, vietnamita, coreano, tailandese, greco, bulgaro, croato, slovacca, lituano, filippina, lettone, estone e sloveno. Altre lingue presto.

Le informazioni si basano su articoli di Wikipedia e altri progetti Wikimedia, e sono disponibili sotto la Licenza Creative Commons Attribuzione-Condividi allo stesso modo.

Unionpedia non è supportata o affiliata alla Wikimedia Foundation.

Google Play, Android e il logo di Google Play sono marchi di Google Inc.

Politica sulla riservatezza