eBook ISBN:  9781470439842 
Product Code:  DIMACS/26.E 
List Price:  $138.00 
MAA Member Price:  $124.20 
AMS Member Price:  $110.40 
eBook ISBN:  9781470439842 
Product Code:  DIMACS/26.E 
List Price:  $138.00 
MAA Member Price:  $124.20 
AMS Member Price:  $110.40 

Book DetailsDIMACS  Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 26; 1996; 657 ppMSC: Primary 68; 90
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 graph, and solving instances of the satisfiability problem. These problems were chosen both for their practical interest and because of their theoretical intractability.
Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were copublished with the Association for Computer Machinery (ACM).
ReadershipGraduate students and research mathematicians interested in graph theory and combinatorial optimization.

Table of Contents

Chapters

Introduction to the Second DIMACS Challenge: Cliques, coloring, and satisfiability

Clique

Polyhedral methods for the maximum clique problem

Finding large cliques in arbitrary graphs by bipartite matching

An exact quadratic 01 algorithm for the stable set problem

Camouflaging independent sets in quasirandom graphs

Constructing cliques using restricted backtracking

A continuous based heuristic for the maximum clique problem

Applying the INN model to the maximum clique problem

Experiments with polynomialtime CLIQUE approximation algorithms on very large graphs

Approximately solving maximum clique using neural network and related heuristics

Edge projection and the maximum cardinality stable set problem

Tabu search algorithms for the maximum clique problem

Coloring

Exploring the kcolorable landscape with iterated greedy

Coloring by Tabu branch and bound

Experiments with parallel graph coloring heuristics and applications of graph coloring

Distributed coloration neighborhood search

An improved algorithm for exact graph coloring

Satisfiability

Random generation of test instances with controlled attributes

A linear programming and rounding approach to max 2SAT

SAT versus UNSAT

Large plateaus and plateau search in Boolean satisfiability problems: When to give up searching and start again

Tabu search and a quadratic relaxation for the satisfiability problem

Efficiency and stability of hypergraph SAT algorithms

A GRASP for satisfiability

Local search strategies for satisfiability testing

Simulated annealing for hard satisfiability problems

Satisfiability testing with more reasoning and less guessing

Comparative studies of constraint satisfaction and DavisPutnam algorithms for maximum satisfiability problems

Combination

Objectoriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability

Appendix. Second DIMACS challenge test problems


RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Requests
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 graph, and solving instances of the satisfiability problem. These problems were chosen both for their practical interest and because of their theoretical intractability.
Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were copublished with the Association for Computer Machinery (ACM).
Graduate students and research mathematicians interested in graph theory and combinatorial optimization.

Chapters

Introduction to the Second DIMACS Challenge: Cliques, coloring, and satisfiability

Clique

Polyhedral methods for the maximum clique problem

Finding large cliques in arbitrary graphs by bipartite matching

An exact quadratic 01 algorithm for the stable set problem

Camouflaging independent sets in quasirandom graphs

Constructing cliques using restricted backtracking

A continuous based heuristic for the maximum clique problem

Applying the INN model to the maximum clique problem

Experiments with polynomialtime CLIQUE approximation algorithms on very large graphs

Approximately solving maximum clique using neural network and related heuristics

Edge projection and the maximum cardinality stable set problem

Tabu search algorithms for the maximum clique problem

Coloring

Exploring the kcolorable landscape with iterated greedy

Coloring by Tabu branch and bound

Experiments with parallel graph coloring heuristics and applications of graph coloring

Distributed coloration neighborhood search

An improved algorithm for exact graph coloring

Satisfiability

Random generation of test instances with controlled attributes

A linear programming and rounding approach to max 2SAT

SAT versus UNSAT

Large plateaus and plateau search in Boolean satisfiability problems: When to give up searching and start again

Tabu search and a quadratic relaxation for the satisfiability problem

Efficiency and stability of hypergraph SAT algorithms

A GRASP for satisfiability

Local search strategies for satisfiability testing

Simulated annealing for hard satisfiability problems

Satisfiability testing with more reasoning and less guessing

Comparative studies of constraint satisfaction and DavisPutnam algorithms for maximum satisfiability problems

Combination

Objectoriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability

Appendix. Second DIMACS challenge test problems