A complete resolution of the Keller maximum clique problem
A d-dimensional Keller graph has vertices which are numbered with each of the 4[superscript d] 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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81184 https://orcid.org/0000-0003-4626-5648 |
| _version_ | 1826207738617659392 |
|---|---|
| author | Debroni, Jennifer Eblen, John D. Langston, Michael A. Myrvold, Wendy Shor, Peter W. Weerapurage, Dinesh |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Debroni, Jennifer Eblen, John D. Langston, Michael A. Myrvold, Wendy Shor, Peter W. Weerapurage, Dinesh |
| author_sort | Debroni, Jennifer |
| collection | MIT |
| description | A d-dimensional Keller graph has vertices which are numbered with each of the 4[superscript d] 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. |
| first_indexed | 2024-09-23T13:54:11Z |
| format | Article |
| id | mit-1721.1/81184 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:54:11Z |
| publishDate | 2013 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/811842022-09-28T16:56:58Z A complete resolution of the Keller maximum clique problem Debroni, Jennifer Eblen, John D. Langston, Michael A. Myrvold, Wendy Shor, Peter W. Weerapurage, Dinesh Massachusetts Institute of Technology. Department of Mathematics Shor, Peter W. A d-dimensional Keller graph has vertices which are numbered with each of the 4[superscript d] 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. Natural Sciences and Engineering Research Council of Canada (Discovery Grant) National Science Foundation (U.S.) (Grant CCF-0829421) National Institutes of Health (U.S.) (Grant AA016662) United States. Dept. of Energy. EPSCoR Laboratory Partnership Program 2013-09-25T20:38:26Z 2013-09-25T20:38:26Z 2011 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/81184 Jennifer Debroni, John D. Eblen, Michael A. Langston, Wendy Myrvold, Peter Shor, and Dinesh Weerapurage. 2011. A complete resolution of the Keller maximum clique problem. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11). SIAM 129-135. Copyright © SIAM 2011 https://orcid.org/0000-0003-4626-5648 en_US http://dl.acm.org/citation.cfm?id=2133047 Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '11 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for Computing Machinery (ACM) SIAM |
| spellingShingle | Debroni, Jennifer Eblen, John D. Langston, Michael A. Myrvold, Wendy Shor, Peter W. Weerapurage, Dinesh A complete resolution of the Keller maximum clique problem |
| title | A complete resolution of the Keller maximum clique problem |
| title_full | A complete resolution of the Keller maximum clique problem |
| title_fullStr | A complete resolution of the Keller maximum clique problem |
| title_full_unstemmed | A complete resolution of the Keller maximum clique problem |
| title_short | A complete resolution of the Keller maximum clique problem |
| title_sort | complete resolution of the keller maximum clique problem |
| url | http://hdl.handle.net/1721.1/81184 https://orcid.org/0000-0003-4626-5648 |
| work_keys_str_mv | AT debronijennifer acompleteresolutionofthekellermaximumcliqueproblem AT eblenjohnd acompleteresolutionofthekellermaximumcliqueproblem AT langstonmichaela acompleteresolutionofthekellermaximumcliqueproblem AT myrvoldwendy acompleteresolutionofthekellermaximumcliqueproblem AT shorpeterw acompleteresolutionofthekellermaximumcliqueproblem AT weerapuragedinesh acompleteresolutionofthekellermaximumcliqueproblem AT debronijennifer completeresolutionofthekellermaximumcliqueproblem AT eblenjohnd completeresolutionofthekellermaximumcliqueproblem AT langstonmichaela completeresolutionofthekellermaximumcliqueproblem AT myrvoldwendy completeresolutionofthekellermaximumcliqueproblem AT shorpeterw completeresolutionofthekellermaximumcliqueproblem AT weerapuragedinesh completeresolutionofthekellermaximumcliqueproblem |