Practical graph isomorphism, II

Practical graph isomorphism, II

9 January 2013 | Brendan D. McKay, Adolfo Piperno
The paper provides an overview of the practical aspects of the graph isomorphism problem, focusing on the refinement-individualization paradigm and its implementation in key programs such as nauty and Traces. The authors describe the general principles of the paradigm, its validity, and its implementation in various programs. They update the description of nauty and introduce Traces, an innovative approach that outperforms competitors for many difficult graph classes. Detailed comparisons are presented against saucy, Bliss, and conauto. The paper also discusses the generic algorithm, including colorings, group actions, and the search tree, and provides implementation strategies for nauty and Traces. The performance of the programs is evaluated on a variety of graph families, highlighting the strengths and weaknesses of each.The paper provides an overview of the practical aspects of the graph isomorphism problem, focusing on the refinement-individualization paradigm and its implementation in key programs such as nauty and Traces. The authors describe the general principles of the paradigm, its validity, and its implementation in various programs. They update the description of nauty and introduce Traces, an innovative approach that outperforms competitors for many difficult graph classes. Detailed comparisons are presented against saucy, Bliss, and conauto. The paper also discusses the generic algorithm, including colorings, group actions, and the search tree, and provides implementation strategies for nauty and Traces. The performance of the programs is evaluated on a variety of graph families, highlighting the strengths and weaknesses of each.
Reach us at info@study.space
[slides and audio] Practical graph isomorphism%2C II