Fredrik Stenkvist: Graph isomorphism algorithms in nauty
Tid: Fr 2018-06-15 kl 14.30 - 15.30
Plats: Room 22, House 5, Kräftriket, Department of Mathematics, Stockholm University
Respondent: Fredrik Stenkvist (BSc student)
Handledare: Jorgen Backelin
Abstract:
The graph isomorphism problem, the problem of determining if two given graphs are the same up to a relabelling of the vertices, is a very important problem in graph theory. One of the best algorithms forpractical use is the nauty algorithm. The subject of this paper is to show how the nauty algorithm works, discuss some of its strengths and weaknesses and show how it handles some common families of graphs. The nauty algorithm is a backtracking algorithm which creates a canonical labelling for a graph. Then one can easily check if two graphs are isomorphic by checking if they get the same canonical labelling. It handles graphs which have vertices of many different degrees very fast, while it has more problems with graphs which are regular and which have large automorphism groups.