Graph Isomorphism Problem

Question

I am doing some literature review on Graph isomorphism problem. Most of papers which I am reading are written by E.M Luks and Laszlo Babai. These papers uses the high level knowledge of group theory and complexity theory. As I am new to this field many of the things are not clear to me.

Can some one suggest me a way to learn ideas and techniques which are presented in these papers so that I can come up with some other ideas.

Thank you so much

See also related question http://cstheory.stackexchange.com/q/12369/ — András Salamon, Apr 05 '14 at 14:56

score 20 · Accepted Answer · edited Dec 24 '15 at 14:29

20

I highly recommend Paolo Codenotti's thesis for the group-theoretic aspects, and the book The Graph Isomorphism Problem: Its Structural Complexity by Johannes Köbler, Uwe Schöning, and Jacobo Torán for the complexity aspects.

edited Dec 24 '15 at 14:29

Sasho Nikolov

18,189
2
67
115

answered Sep 06 '13 at 15:40

Joshua Grochow

37,260
4
129
228

score -4 · Answer 2 · answered Sep 07 '13 at 02:23

-4

http://oeis.org/A186202 is the best you can do for automorphism by brute force permutation checking.

answered Sep 07 '13 at 02:23

Chad Brewbaker

2,359
15
18

Graph Isomorphism Problem

2 Answers2