Pagina Radice del Progetto: Ricerca di Sottografi Isomorfi in grafi planari

Dati due grafi G ed H, determinare se essi siano isomorfi, ossia se essi siano lo stesso grafo a seguito di un'opportuna permutazione dei nodi, è un famigerato problema in teoria della complessità. Se uno dei due grafi è una costante che non fa parte dell'input, allora il problema è ovviamente polinomiale. Ma di che grado? Vorremmo implementare un algoritmo proposto di recente e che cerca di contenere il valore del grado del polinomio, almeno per grafi planari.

Eppstein, David
Subgraph isomorphism in planar graphs and related problems.
J. Graph Algorithms Appl. 3 (1999), no. 3, 27 pp.

created: 26 Aprile 2001
updated: 26 Aprile 2001