Second DIMACS Challenge
Cliques, Graph Coloring, and Satisfiability

Update: September 19, 1993

A couple reminders:

The Challenge Conference will be held  October 11-13 at the DIMACS
Conference Center, Rutgers University.  Be sure to register in advance
(by writing toci@dimacs.rutgers.edu).  You should have received a call
for participation last week.  If you did not, please contact me, or
pick it up from the Challenge archives.

All comments on the papers submitted for presentation were sent out
last week.  If you submitted a paper and did not receive your
comments, please contact me immediately.  Also, if your paper was
accepted, please send me a "normal" mail address if you have not
already done so.  If your paper has been accepted and you will not be
able to present, please let me know _immediately_ so we can make
alternative plans.

Finally, we have a limited amount of travel funds available to support
researchers in attending the Challenge Conference.  You can apply for
these funds simply by contacting me at challenge@dimacs.rutgers.edu.
Graduate students are particularly encouraged to apply for support if
needed.

There are a number of new files this time around (all via anonymous
ftp from dimacs.rutgers.edu in the pub/challenge directory):

graph/solvers/:  Two clique solvers have been provided by the Steering
committee to standardize testing.  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.
Comments and bug reports can be sent to me or David Johnson
(dsj@research.att.com).  

graph/translators/: asc2bin.c had a bug in it for some compilers
(which causes infinite looping).  This has been corrected.

graph/contributed/mannino: Carlo Mannino (mannino@iasi.rm.cnr.it) has
submitted C code to translate set covering type problems to clique
problems.

There are also some new instances in the benchmarks and some new
solutions for the clique instances.  If I have neglected to handle
something you have submitted, please let me know:  it has been a bit
hectic getting the conference together and I may have forgotten
something.

I hope to see many of you in a month!

                                  Mike Trick
                                  Challenge Coordinator/
                                     Carnegie Mellon University