|
%I #23 Jun 18 2022 00:17:10
%S 1,1,2,2,2,4,5,7,11,16,24
%N Maximal size of binary code of length n that corrects 2 deletions.
%C Comments from Pablo San Segundo, Dec 04 2015 (Start): The search for a maximal clique in the graph 2dc.2048 has now finished. The answer is 24 (which was already known to be a lower bound).
%C The total time was 16.4 days using a 20-core XEON with 128Gb. 18 cores out of the 20 were in fact used.
%C The solution was found by a strong heuristic algorithm during pre-processing (about 5s). The actual search time was used "only" to prove optimality. The actual maximum clique algorithm is our most recent variant based on infra-chromatic BBMCX, described here, but as yet unpublished: https://www.researchgate.net/profile/Pablo_San_Segundo
%C The project was carried out by Pablo San Segundo and Jorge Artieda, Polytechnic University of Madrid (UPM), Center of Automation and Robotics (CAR). Supported by National Grant DPI 2014-53525-C3-1-R (End)
%H N. J. A. Sloane, <a href="/A265032/a265032.html">Challenge Problems: Independent Sets in Graphs</a>
%H N. J. A. Sloane, <a href="http://arxiv.org/abs/math/0207197">On single-deletion-correcting codes</a>, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/dijen.txt">On single-deletion-correcting codes</a>
%Y Cf. A000016, A057608, A057657, A010101.
%K nice,hard,nonn
%O 1,3
%A _N. J. A. Sloane_, Oct 05 2000
%E Guenter Stertenbrink (Sterten(AT)aol.com) found a(9) = 11 and a(10) >= 16, Apr 28 2001
%E James B. Shearer (jbs(AT)pkmfgvm4.vnet.ibm.com) proved that a(10) = 16, Sep 20 2003
%E Pablo San Segundo and Jorge Artieda showed that a(11) = 24, Dec 04 2015
| 