Metraipolis › archive › dc_bbf2370397af

Algoritmo di Ullmann — Wikipedia

Source: Wikipedia (it)
Original: https://it.wikipedia.org/wiki/Algoritmo_di_Ullmann
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-15T16:25:25.110Z
SHA-256 of the archived text: 50a73606425adeaa225ebead52d7e329bf8acef589544d103a0ef8c4a0f98342
Stable URL of this page: https://metraipolis.com/documento/dc_bbf2370397af

How to cite

Algoritmo di Ullmann — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Ullmann (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_bbf2370397af (Metraipolis archive dc_bbf2370397af, sha256 50a73606425adeaa225ebead52d7e329bf8acef589544d103a0ef8c4a0f98342)

BibTeX

@misc{dcbbf2370397af,
  title = {Algoritmo di Ullmann — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Algoritmo_di_Ullmann},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_bbf2370397af; sha256 50a73606425adeaa225ebead52d7e329bf8acef589544d103a0ef8c4a0f98342},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Ullmann. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. 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 legami covalenti.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «Algoritmo di Ullmann» — https://it.wikipedia.org/wiki/Algoritmo_di_Ullmann
Wikidata Q3611586 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q3611586
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_Ullmann?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 143990229, consultata il 2026-10-15T16:00:47.558Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 9207ef3667bbfd1777fba52d3855b834fb7220cc1a84348ba0c2696f12df8b78