DCI'00

Giovanni Di Crescenzo

Telcordia Technologies

The Graph Isomorphism Problem


The Graph Isomorphism Problem is a classical problem in Graph Theory. It consists of determining whether two input graphs are `essentially' the same graph. In this talk we will discuss algorithms for solving this problem, connections between this problem and various areas of Theoretical Computer Science and applications of this problem in various settings.