\documentstyle[12pt,supertab]{article} \begin{document} \tablefirsthead{\hline\multicolumn{5}{|c|}{DIMACS CLIQUE BENCHMARKS}\\\hline File&Code&Nodes&Edges&Clique Size\\\hline} \tablehead{\hline\multicolumn{5}{|c|}{DIMACS CLIQUE BENCHMARKS (cont.)}\\\hline File&Code&Nodes&Edges&Clique Size\\\hline} \tabletail{\hline\multicolumn{5}{|r|}{\it Continued on next page}\\\hline} \tablelasttail{\hline} \begin{supertabular}{|lc|rr|c|} c-fat200-1.clq&(CFat)&200&1534&\\ c-fat200-2.clq&(CFat)&200&3235&\\ c-fat200-5.clq&(CFat)&200&8473&\\ c-fat500-1.clq&(CFat)&500&4459&\\ c-fat500-10.clq&(CFat)&500&46627&\\ c-fat500-2.clq&(CFat)&500&9139&\\ c-fat500-5.clq&(CFat)&500&23191&\\ johnson16-2-4.clq&(Joh)&120&5460&8\\ johnson32-2-4.clq&(Joh)&496&107880&\\ johnson8-2-4.clq&(Joh)&28&210&\\ johnson8-4-4.clq&(Joh)&70&1855&14\\ keller4.clq&(Kel)&171&9435&11\\ keller5.clq&(Kel)&776&225990&27\\ keller6.clq&(Kel)&3361&4619898&$\ge$ 59\\ hamming10-2.clq&(Ham)&1024&518656&\\ hamming10-4.clq&(Ham)&1024&434176&\\ hamming6-2.clq&(Ham)&64&1824&32\\ hamming6-4.clq&(Ham)&64&704&4\\ hamming8-2.clq&(Ham)&256&31616&$\ge$ 79\\ hamming8-4.clq&(Ham)&256&20864&16\\ san1000.clq&(San)&1000&250500&15\\ san200\_0.7\_1.clq&(San)&200&13930&30\\ san200\_0.7\_2.clq&(San)&200&13930&18\\ san200\_0.9\_1.clq&(San)&200&17910&70\\ san200\_0.9\_2.clq&(San)&200&17910&60\\ san200\_0.9\_3.clq&(San)&200&17910&44\\ san400\_0.5\_1.clq&(San)&400&39900&13\\ san400\_0.7\_1.clq&(San)&400&55860&40\\ san400\_0.7\_2.clq&(San)&400&55860&30\\ san400\_0.7\_3.clq&(San)&400&55860&22\\ san400\_0.9\_1.clq&(San)&400&71820&100\\ sanr200\_0.7.clq&(San)&200&13868&\\ sanr200\_0.9.clq&(San)&200&17863&\\ sanr400\_0.5.clq&(San)&400&39984&\\ sanr400\_0.7.clq&(San)&400&55869&\\ brock200\_1.clq.b&(Bro)&200 &14834 &21 \\ brock200\_2.clq.b&(Bro)&200 &9876 &12 \\ brock200\_3.clq.b&(Bro)&200 &12048 &15 \\ brock200\_4.clq.b&(Bro)&200 &13089 &17 \\ brock400\_1.clq.b&(Bro)&400 &59723 &27 \\ brock400\_2.clq.b&(Bro)&400 &59786 &29 \\ brock400\_3.clq.b&(Bro)&400 &59681 &31 \\ brock400\_4.clq.b&(Bro)&400 &59765 &33 \\ brock800\_1.clq.b&(Bro)&800 &207505 &23 \\ brock800\_2.clq.b&(Bro)&800 &208166 &24 \\ brock800\_3.clq.b&(Bro)&800 &207333 &25 \\ brock800\_4.clq.b&(Bro)&800 &207643 &26 \\ p\_hat300-1.clq&(PHat)&300 &10933 & \\ p\_hat300-2.clq&(PHat)&300 &21928 & \\ p\_hat300-3.clq&(PHat)&300 &33390 & \\ p\_hat500-1.clq&(PHat)&500 &31569 & \\ p\_hat500-2.clq&(PHat)&500 &62946 & \\ p\_hat500-3.clq&(PHat)&500 &93800 & \\ p\_hat700-1.clq&(PHat)&700&60999& \\ p\_hat700-2.clq&(PHat)&700&121728& \\ p\_hat700-3.clq&(PHat)&700&183010& \\ p\_hat1000-1.clq&(PHat)&1000 &122253 & \\ p\_hat1000-2.clq&(PHat)&1000 &244799 & \\ p\_hat1000-3.clq&(PHat)&1000 &371746 & \\ p\_hat1500-1.clq&(PHat)&1500 &284923 & \\ p\_hat1500-2.clq&(PHat)&1500 &568960 & \\ p\_hat1500-3.clq&(PHat)&1500 &847244 & \\ MANN\_a27.clq&(Stein)&378&70551&126\\ MANN\_a45.clq&(Stein)&1035&533115&345\\ MANN\_a81.clq&(Stein)&3321&5506380&$\ge$1100\\ MANN\_a9.clq&(Stein)&45&918&16\\ \end{supertabular} \bigskip \noindent {\bf Notes:} \begin{description} \item[CFat] (From Panos Pardalos {\tt pardalos@math.uflorida.edu}) Problems based on fault diagnosis problems. Original reference is Berman and Pelc, ``Distributed Fault Diagnosis for Multiprocessor Systems,'' {\it Proceedings of the 20th Annual Symposium on Fault--Tolerant Computing}, 340--346 (1990). For more instances, see the generator in graph/contributed/pardalos. \item[Joh] (From Panos Pardalos {\tt pardalos@math.uflorida.edu}) Problems based on problem in coding theory. A Johnson graph with parameters $n, w, d$ has a node for every binary vector of length $n$ with exactly $w$ 1s. Two vertices are adjacent if and only if their hamming distance is at least $d$. A clique then represents a feasible set of vectors for a code. For more instances, see the generator in graph/contributed/pardalos. \item[Kel] (From Peter Shor {\tt shor@research.att.com}) Problems based on Keller's conjecture on tilings using hypercubes. One reference is J.C. Lagarias and P.W. Shor, ``Keller's Cube--Tiling Conjecture is False in High Dimensions,'' {\it Bulletin of the AMS}, {\bf 27:} 279--283 (1992). For more instances (though they get very large very fast) see either the generator in graph/contributed/shor or the generator in graph/contributed/pardalos. \item[Ham] (From Panos Pardalos {\tt pardalos@math.uflorida.edu}) Another coding theory problem. A Hamming graph with parameters $n$ and $d$ has a node for each binary vector of length $n$. Two nodes are adjacent if and only if the corresponding bit vectors are hamming distance at least $d$ apart. For more instances, see the generator in graph/contributed/pardalos. It has been noted by participants that $n--2$ graphs have a maximum clique of size $2^{n-1}$. For a proof of this, see the note in graph/contributed/bourjolly/hamming.tex. \item[San] (From Laura Sanchis {\tt laura@cs.colgate.edu}) Instances based on her ``Test Case Construction for Vertex Cover Problem,'' DIMACS Workshop on Computational Support for Discrete Mathematics, March 1992 along with more recent work that will be part of a technical report to be published. The generator generates instances with known clique size. \item[SanR] (From Laura Sanchis {\tt laura@cs.colgate.edu}) These are random instances with sizes similar to those in {\bf San}. \item[Bro] (From Mark Brockington {\tt brock@cs.ualberta.ca}) Instances from Mark Brockington and Joe Culberson's generator that attempts to ``hide'' cliques in a graph where the expected clique size is much smaller. For more instances, see their generator in graph/contributed/brockington. \item [PHat] (From Patrick Soriano and Michel Gendreau {\tt patrick@crt.umontreal.ca}) Random problems generated with the p\_hat generator which is a generalization of the classical uniform random graph generator. Uses 3 parameters: $n$, the number of nodes, and $a$ and $b$, two density parameters verifying $0 \le a \le b \le 1$. Generates problem instances having wider node degree spread and larger clique sizes. Reference: "Solving the Maximum Clique Problem Using a Tabu Search Approach", {\em Annals of Operations Research} {\bf 41}, 385--403 (1993). \item[Stein] (From Carlo Mannino {\tt mannino@iasi.rm.cnr.it}) Clique formulation of the set covering formulation of the Steiner Triple Problem. Created using Mannino's code to convert set covering problems to clique problems. \end{description} \end{document}