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

Front Cover
David S. Johnson, Michael A. Trick
American Mathematical Soc., Jan 1, 1996 - Mathematics - 657 pages
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Polyhedral methods for the maximum clique problem
11
Finding large cliques in arbitrary graphs by bipartite matching
29
Edge projection and the maximum cardinality stable set problem
51
An exact quadratic 01 algorithm for the stable set problem
53
Camouflaging independent sets in quasirandom graphs
75
Constructing cliques using restricted backtracking
89
A continuous based heuristic for the maximum clique problem
103
Applying the INN model to the Maximum Clique problem
125
An improved algorithm for exact graph coloring
359
Random generation of test instances with controlled attributes
377
A linear programming and rounding approach to max 2sat
395
SAT versus UNSAT
415
When
437
Simulated annealing for hard satisfiability problems
453
Tabu search and a quadratic relaxation for the Satisfiability problem
457
Efficiency and stability of hypergraph SAT algorithms
479

Experiments with polynomialtune CLIQUE approximation algorithms
147
Approximately solving Maximum Clique using neural network and related
169
Tabu search algorithms for the maximum clique problem
221
Coloring
228
Exploring the Acolorable landscape with Iterated Greedy
245
Coloring by tabu branch and bound
285
Experiments with parallel graph coloring heuristics and applications
309
Distributed coloration neighborhood search
335
A GRASP for satisfiability
499
Local search strategies for satisfiability testing
521
Satisfiability testing with more reasoning and less guessing
559
Comparative studies of constraint satisfaction and DavisPutnam algo
587
Objectoriented implementation of heuristic search methods for Graph Coloring
619
Second DIMACS Challenge test problems
653
Copyright

Common terms and phrases

Popular passages

Page 6 - 82 Symposium on Compiler Construction, pages 98-101, June 1982.

Bibliographic information