chapter  2.2
9 Pages

Graph Isomorphism

WithBrendan D. McKay

Isomorphism between graphs and related objects is a fundamental concept in graph theory and its applications to other parts of mathematics. The problem also occupies a central position in complexity theory as a proposed occupant of the region that must exist between the polynomial-time and NP-complete problems if P≠NP. Due to its many practical applications a considerable number of algorithms for graph isomorphism have been proposed.