Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
复制标题
规范颜色细化复杂性的严格下限和上限
DOI：
--
复制
发表时间：
2013
影响因子：
0.5
通讯作者：
Martin Grohe
中科院分区：
文献类型：
--
作者：
Christoph Berkholz;P. Bonsma;Martin Grohe
如果任意两个相同颜色的顶点具有相同颜色的邻域，则图形顶点的颜色分配是稳定的。色彩细化的目标是找到一种使用最少颜色的稳定着色。这是一个广泛应用于图同构测试算法的子程序，因为任何自同构都需要保持颜色。我们给出了一个O（(m + n)log n）算法，用于在有n个顶点和m条边的图上寻找这种稳定着色的规范版本。我们表明，在对算法类型的一些适度假设下，没有更快的算法是可能的，它捕获了所有已知的颜色细化算法。
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an O((m + n)log n) algorithm for finding a canonical version of such a stable colouring, on graphs with n vertices and m edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.