Algoritmo di Ullmann: differenze tra le versioni

Versione delle 08:54, 25 set 2019

Versione attuale delle 07:53, 13 mar 2025

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 [[polinomio|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]].

L'algoritmo di Ullmann trova applicazione nella [[chemioinformatica]], 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]].<ref>{{cita pubblicazione|autore=J. R. Ullmann|titolo=An Algorithm for Subgraph Isomorphism|rivista=Journal of the ACM|volume=23|numero=1|pp=31–4231-42|anno=1976|url=http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/Ullman_Algorithm.pdf|accesso=11 giugno 2013|urlarchivio=https://web.archive.org/web/20131029205845/http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/Ullman_Algorithm.pdf|dataarchivio=29 ottobre 2013|urlmorto=sì}}</ref>

==Algoritmo di Ullman in chemioinformatica==