Practical graph isomorphism, II

Practical graph isomorphism, II

9 January 2013 | Brendan D. McKay, Adolfo Piperno
The paper discusses the practical aspects of the graph isomorphism problem, focusing on the refinement-individualization paradigm and its implementation in key programs like nauty and Traces. It explains how these programs determine whether two graphs are isomorphic, with nauty being a well-known program that uses automorphisms to prune search spaces. Traces, an innovative approach, outperforms other programs for many difficult graph classes by using a different tree scanning strategy. The paper compares the performance of nauty and Traces with Bliss, saucy, and conauto on various graph families, showing that nauty is generally faster for small graphs and some easier families, while Traces excels for difficult ones. The paper also describes the theoretical foundations of the refinement-individualization paradigm, including colorings, group actions, and search trees, and discusses implementation strategies for these algorithms. It highlights the importance of pruning techniques and node invariants in improving efficiency. The paper concludes that Traces is currently the leader for most difficult graph classes, while nauty remains preferred for mass testing of small graphs.The paper discusses the practical aspects of the graph isomorphism problem, focusing on the refinement-individualization paradigm and its implementation in key programs like nauty and Traces. It explains how these programs determine whether two graphs are isomorphic, with nauty being a well-known program that uses automorphisms to prune search spaces. Traces, an innovative approach, outperforms other programs for many difficult graph classes by using a different tree scanning strategy. The paper compares the performance of nauty and Traces with Bliss, saucy, and conauto on various graph families, showing that nauty is generally faster for small graphs and some easier families, while Traces excels for difficult ones. The paper also describes the theoretical foundations of the refinement-individualization paradigm, including colorings, group actions, and search trees, and discusses implementation strategies for these algorithms. It highlights the importance of pruning techniques and node invariants in improving efficiency. The paper concludes that Traces is currently the leader for most difficult graph classes, while nauty remains preferred for mass testing of small graphs.
Reach us at info@study.space
Understanding Practical graph isomorphism%2C II