Last Update November 28, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) graph/contributed/culberson/color.Nov2893.bib: Updated bibliography on graph coloring. graph/contributed/culberson/gen.c: Generator to create coloring problems (some generated instances in benchmarks). graph/contributed/sanchis: Generator to create clique instances with known optimal clique values. sat/contributed/zuazaga: Solution code to solve satisfiability problems using a hill climbing procedure. sat/contributed/miyano: Random satisfiability instances (many in the benchmarks). sat/contribued/dubois: Solution code to solve satisfiability problems using a variant of the Davis-Putnam procedure. Last update September 19, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) graph/solvers: From David Johnson (dsj@research.att.com). Two solution codes for cliques have been provided by the Steering Committee. These are dfmax.c, a simple-minded branch-and-bound code and dmclique.c, a variant on the simple "semi-exhaustive greedy" scheme for finding large independent sets. graph/translators/: A bug in asc2bin.c has been fixed (caused infinite loops for some compilers. graph/contributed/mannino/: Caro Mannino (mannino@iasi.rm.cnr.it) has submitted code to translate set covering problems to clique problems in the DIMACS format. Instances based on the Steiner Triple problem have been included in the benchmarks Last update August 22, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) graph/contributed/soriano: From Patrick Soriano (patrick@crt.umontreal.edu): A generator in PASCAL for clique instances as described in "Solving the maximum clique problem using a tabu search approach" Annals of OR 41 385-403. Some instances are included in the benchmarks. sat/contributed/iwama: From Kazuo Iwama (iwama@csce.kyushu-u.ac.jp): Two generators (one for satisfiable and one for unsatisfiable instances) with control on attributes of instances. Some instances will be included in benchmarks when I figure out what would be some interesting instances. iwama_prog.sh is a shell file, extracted by the command: sh iwama_prog.sh sat/contributed/pretolani: From Daniele Pretolani (daniele@crt.umontreal.edu): Two generators (source code) and two exact solution codes (Sun Sparc executable only) for satisfiability. One generator is for k-SAT formulae where the number of literals in each clause is uniformly distributed, while the other is based on graph 2-coloring with a parity contraint (the latter determines whether the instance is satisfiable or not). Instances of the second class are in the benchmarks. sat/contributed/zhang: From Hantao Zhang (hzhang@cs.uiowa.edu). Contains source for "sato", a decision procedure for propositional logic. Last update July 29, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) graph/benchmarks/clique: Additional instances graph/benchmarks/sat: Additional instances sat/contributed/crawford/tableau.ps: A paper from James Crawford (jc@research.att.com) describing the behavior of satisfiability problems as a function of instance size. graph/contributed/brockington/graphgen.c: From Mark Brockington (brock@cs.ualberta.ca). A graph generator that hides large cliques in graphs. Last update July 11, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) call_paper.asc: Call for Papers for the October 11-13 conference (due date : August 3, 1993). graph/translators/binformat: Description and code for a compressed graph format. The result is a file many times smaller for graphs of even moderate density. The resulting graph is denoted by a .b suffix graph/benchmarks/clique: Initial benchmark graphs for the clique problem. graph/benchmarks/color: Initial benchmark graphs for the coloring problem. sat/benchmarks/cnf: Initial benchmark graphs in conjunctive normal form. sat/benchmarks/sat: Other satisfiability benchmarks sat/contributed/barth/dp02.tar: dp.c had a bug that limited its use to 4096 clauses. The updated version has fixed that problem. sat/contributed/UCSC/instances: Contributed by Allen Van Gelder at UCSC (avg@cs.ucsc.edu. A large number of instances for sat (in cnf format) based on fault recognition. There is also a new parser, replacing the previous version. Remember to use binary format when transferring either .Z or .tar files via ftp. Some of these instances will also appear in the sat/benchmarks directory. Last update June 9, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) sat/contributed/UCSC/parser/: parser from Allen Van Gelder (avg@cs.ucsc.edu). sat/translators/: codes to translate from cnf format to sat format, and from conjunctive normal form expressions in sat format to cnf format by Tamas Badics (badics@rutcor.rutgers.edu). graph/contributed/pardalos/*.f: A number of generators for clique problems from Panos Pardalos (pardalos@math.ufl.edu). sat/contributed/dubois/gensathard.c: generator from Olivier Dubois (dubois@laforia.ibp.fr) that generates hard sat problems. sat/contributed/barth/dp02.tar: Implementation of Davis Putnam from Peter Barth (barth@mpi-sb.mpg.de), including many heuristic additions. graph/contributed/lewandowski/reg.shar: generators and test problems for coloring register allocation graphs from Gary Lewandowski (gary@cs.wisc.edu). sat/contributed/stamm-wilbrandt/IAI-TR-93-3.ps: A technical report from Hermann Stamm-Wilbrandt (hermann@holmium.informaik.uni-bonn.de) that gives a number of reductions from hard and easy problems to satisfiability. Last update May 8, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) sat/doc/satformat.tex: Updated version of the satisfiability format. graph/doc/ccformat.tex: Minor update of graph format (parameter lines begin with "x"). sat/contributed/barth/: Files from Peter Barth (barth@mpi-sb.mpg.de) with an implementation of the Davis--Putnam procedure. graph/contributed/jagota/newgenerators.shar: Files from Arun Jagota (jagota@cs.buffalo.edu) giving updated generators, seeds, and other information for comparison with his work. Last update March 28, 1993 MT The following additons and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) ls-lR: A recursive listing of all the files and directories under pub/challenge. sat/doc/satformat.tex: A proposed format for satisfiability instances. Actually, two formats are suggested: one specifically for instances in conjunctive normal form, and one that can handle more general instances. sat/contributed/naylor/: From William Naylor (naylor@research.canon.oz.au). This directory contains a program which translates integer questions into satisfiability problems. graph/contributed/shor/: From Peter SHor (shor@research.att.com). A program and two clique instances generated from that program. These instances relate to the Keller conjecture. Last update: March 12, 1993 MT The following additions and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) proposals/: The set of proposals submitted in January (seven other proposals did not want to be made available for ftp). These are divided into "graph" (for clique and coloring proposals) and "sat" (for satisfiability proposals). A file with a one paragraph description of each proposal is being prepared. contributed/hooker: A very nice paper from John Hooker (jh38+@andrew.cmu.edu) entitled "Needed: An Empirical Science of Algorithms" that I found to be very relevant to the Challenge. graph/contributed/culberson: Submitted by Joe Culberson of the University of Alberta (joe@cs.ualberta.ca). An extensive bibliography on graph coloring algorithms and applications. graph/contributed/morgenstern: Submitted by Craig Morgenstern of TCU (morgenst@riogrande.cs.tcu.edu). A tremendous number of generators and algorithms for graph coloring. The easiest way to get these is to get the" tarred and compressed" files that end .tar.Z morgenstern.tar.Z morgenstern1.tar.Z morgenstern3.tar.Z morgenstern4.tar.Z sat/contributed/dubois: A collection of routines submitted by Prof O. Dubois (dubois@laforia.ibp.fr) for generating and solving satisfiability problems. Last update: February 4, 1993 MT The following additions and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) sat/contributed/gent/: Work from Ian Gent and coauthors at the University of Edinburgh on Hill Climbing methods for SAT. Last update: January 9, 1993 MT The following additions and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) graph/contributed/mannino/: Work from Carlo Mannino of the Universit\'a di Roma La Spienza. A joint paper with Antonio Sassano on an exact algorithm for stable sets. Last update: December 11, 1992 MT The following additions and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu) call_abstract.asc: Instructions for submitting abstracts for review (due date January 15, 1993, modified from previous due date of December 31, 1992). Last update: December 3, 1992 MT The following additions and changes have been made (all in the directory pub/challenge at dimacs.rutgers.edu: graph/doc/ccreview.bib: corrected typos and added references graph/doc/ccreview.tex: a few additions on graph coloring sat/: directory added (link to satisfiability) sat/contributed/selman/: method for generating random hard sat problems; paper on a local search method for SAT. graph/doc/ccformat.tex: Standard modified to allow information on embedding graphs and other parameters used to generate graphs sat/doc/satreview.tex .dvi .ps: Problem definitions, suggested readings, list of suggested projects. Last update: Nov 21, 1992 MT The following new documents are available by ftp from dimacs.rutgers.edu (all in the directory pub/challenge): graph/doc/ccreview.tex: A review of past work on finding cliques and coloring graphs. This is a work in progress that will be updated as more information becomes available. This paper also has more than a dozen suggested research projects. Please write to challenge@dimacs.rutgers.edu if you have additional references or suggested research topics. graph/doc/ccreview.dvi, graph/doc/review.ps: dvi and postscript versions of above document. graph/doc/ccreview.bib: A BibTeX file of the references in the above. graph/doc/ccannote.tex: A TeX file that prints out all of the references along with a one or two line annotation on most of them. Requires BibTeX (a program normally bundled with TeX and LaTeX) and annotate.bst (below). graph/doc/annotate.bst: A BibTeX style file required for ccannote.tex. graph/doc/ccformat.tex: Suggested graph format consistent with the format used in the First Computational Challenge on networks and matchings. A fairly verbose but flexible format suitable for a variety of graph and network algorithms. Not yet the "official" format, but likely to become so unless strong objections are made. graph/doc/ccformat.dvi, graph/doc/ccformat.ps: dvi and postscript versions of the above document. Panos Pardalos of the University of Florida has sent along a very nice and complete bibliography on the clique problem that he and Jue Xue of Clark University have written. He also has a paper on generating clique problems, and two FORTRAN programs for finding cliques. These are in graph/contributed/pardalos. In addition, Arun Jagota of SUNY Buffalo has sent along some technical reports and source code for using neural nets to solve clique problem and some comments on generating hard instances of combinatorial optimization problems. These have been placed in graph/contributed/jagota.