Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge, October 11-13, 1993

by Michael A. Trick, David S. Johnson (Editor)

The purpose of a DIMACS Challenge is to encourage and coordinate research in the experimental analysis of algorithms. The First DIMACS Challenge encouraged experimental work in the area of network flow and matchings. The Second DIMACS Challenge, on which this volume is based, took place in conjunction with the DIMACS Special Year on Combinatorial Optimization. Addressed here are three difficult combinatorial optimization finding cliques in a graph, coloring the vertices of a graph, and solving instances of the satisfiability problem. These problems were chosen both for their practical interest and because of their theoretical intractability.

657 pages, Hardcover

First published January 1, 1996