The DIMACS Challenge (Clique, Coloring, and Satisfiability)
Call for Papers

Due Date: August 3, 1993

In conjunction with its Special Year on Combinatorial Optimization,
the Center for Discrete Mathematics and Theoretical Computer Science
(DIMACS) has been sponsoring an Implementation Challenge to find
effective optimization and approximation algorithms for the following
NP-hard problems: Maximum Clique, Graph Coloring, and Satisfiability.
This Challenge will culminate in a conference to be held at DIMACS
(New Brunswick, NJ) from October 11 through October 13, 1993.

This is a call for papers for presentation at that conference.  Papers
may be on any subject related to computational methods for the three
Challenge problems.  Submittors need not have taken part in the year's
activities in order to be eligible.

1) Submissions can be made in one of two ways:
   (a) (Preferred) Submissions can be made electronically by sending
the TeX, LaTeX, or AMSLaTeX source to 

                 challenge@dimacs.rutgers.edu

   (b) If this is not possible, a copy of the paper can be sent to

                 DIMACS Challenge
                 DIMACS, Rutgers University
                 Box 1179
                 Piscataway, NJ
                 08855-1179
                 
In this case, please send an electronic mail message to
challenge@dimacs.rutgers.edu to confirm your submission.
                 
2) Papers should be no more than 12 pages long.  

3) Before the paper (in the case of electronic submissions) or in the
confirmation message (in the case of physical submissions), please
provide a short (two or thee sentence) summary to aid classification.
Also, please provide a single electronic mail address for
communication regarding the abstract.

Papers must be received by August 3, 1993 to be eligible for
selection.  Papers selected for presentation at the conference will be
made available in a preliminary conference proceedings that will be
sent to presentors and other registered conference attendees.  There
will also be a refereed conference proceedings to which accepted
papers will be invited.

If you are not familiar with the Challenge, there is material
available for anonymous ftp from dimacs.rutgers.edu in the
/pub/challenge subdirectory that explains more about the Challenge and
provides some supporting materials.  This directory also contains
information about standard formats and benchmark instances.  Please
contact challenge@dimacs.rutgers.edu if you would like to be added to
the mailing list.

ADVISORY BOARD.  Committee members are Vasek Chvatal, Rutgers
University, Bill Cook, Bell Communications Research, David Johnson,
AT\&T Bell Laboratories, Cathy McGeoch, Amherst College, Bob Tarjan,
Princeton University, and Michael Trick, DIMACS Visiting
Fellow/Carnegie Mellon University (Coordinator).

                                   Michael Trick
                                   Carnegie Mellon/
                                     DIMACS Challenge Coordinator