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

David S. Johnson · Michael A. Trick

01/1996 · Center for Discrete Mathematics and Theoretical Computer Science New Brunswick, NJ: DIMACS series in discrete mathematics and theoretical computer science Livro 26 · American Mathematical Soc.

Acerca deste livro eletrónico

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. This 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 problems: finding cliques in a graph, colouring 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.