Algoritmo di Ullmann: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nuova pagina; testo: '''''algoritmo di Ullmann''' è un algoritmo per la soluzione del problema dell'isomorfismo di sottografi. Il problema è NP-completo e l'algoritmo non fornisce una...' |
Nessun oggetto della modifica |
||
Riga 1:
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 [[backtracing]] per diminuire il tempo effettivo di esecuzione, che però non hanno effetto sulla [[complessità asintotica]], che rimane esponenziale.
L'algoritmo di Ullmann trova applicazione nella [[chemoinformatica]], in particolare nella ricerca di specifici frammenti all'interno di una molecola. Una molecola può essere vista tramite la sua formula di struttura, come un [[grafo]] non orientato, i cui vertici sono gli atomi e i cui spigoli sono i [[legame covalente|legami covalenti]].
Riga 13:
==Bibliografia==
* J. R. Ullmann: "An Algorithm for Subgraph Isomorphism". Journal of the ACM, 23(1):31–42, 1976.
[[Categoria: Informatica]]
| |||