Practical graph isomorphism, II
Practical graph isomorphism, II
复制标题
DOI：
10.1016/j.jsc.2013.09.003
复制
发表时间：
2014-01-01
影响因子：
0.7
通讯作者：
Piperno, Adolfo
中科院分区：
文献类型：
--
作者：
McKay, Brendan D.;Piperno, Adolfo
从实用的角度报道了图同构问题的研究现状。在描述了细化-个性化范式的一般原则并证明了其有效性之后，我们解释了它是如何在几个关键实现中实现的。特别是，我们带来了最著名的程序nauty的最新描述，并描述了一种称为Traces的创新方法，该方法在许多困难的图类中优于竞争对手。并将其与saucy、Bliss和conauto进行了详细的比较。(C) 2013 Elsevier B.V.版权所有
We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key implementations. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented. (C) 2013 Elsevier B.V. All rights reserved.