Cliques, Coloring, and Satisfiability Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993 |
|
| Editor:
| Johnson, David J.
Trick, Michael A. |
| Series title: | DIMACS: Ser. in Discrete Mathematics and Theoretical Computer Science Ser. |
| ISBN: | 978-0-8218-6609-2 |
| Publication Date: | Oct 1996 |
| Publisher: | American Mathematical Society
|
| Book Format: | Hardback |
| List Price: | USD $131.00 |
Book Description:
|
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 problems: finding cliques in a graph, coloring the vertices of a...
More DescriptionThe 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 problems: 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.