Isomorfismo di sottografi

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Abbozzo
Questa voce sull'argomento matematica dell'informazione e della comunicazione è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

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.

Voci correlate[modifica | modifica wikitesto]

Estratto da "https://it.wikipedia.org/w/index.php?title=Isomorfismo_di_sottografi&oldid=77146471"