A complete resolution of the Keller maximum clique problem
A complete resolution of the Keller maximum clique problem
复制标题
凯勒最大集团问题的彻底解决
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Dinesh Weerapurage
中科院分区：
文献类型：
--
作者：
Jennifer Debroni;John D. Eblen;M. Langston;Wendy J. Myrvold;P. Shor;Dinesh Weerapurage
d维Keller图的顶点由4d可能的d位数（d元组）中的每一个编号，其中每个数字等于0,1,2或3。如果两个顶点的标签至少在两个位置上不同，则它们相邻，并且在至少一个位置上，标签的差异为2模4。Keller图是DIMACS团挑战中的团问题的基准集，对于团算法来说，它们似乎特别困难。七维情况是最后一个不知道最大团阶的凯勒图。据称，为了解决最后一个问题，可能需要一台“大星系大小的高速计算机”。本文描述了我们用来确定第7维团的最大阶数为124的计算。
A d-dimensional Keller graph has vertices which are numbered with each of the 4d possible d-digit numbers (d-tuples) which have each digit equal to 0, 1, 2, or 3. Two vertices are adjacent if their labels differ in at least two positions, and in at least one position the difference in the labels is two modulo four. Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge, and they appear to be especially difficult for clique algorithms. The dimension seven case was the last remaining Keller graph for which the maximum clique order was not known. It has been claimed in order to resolve this last case it might take a "high speed computer the size of a major galaxy". This paper describes the computation we used to determine that the maximum clique order for dimension seven is 124.