## Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993The 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

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 |

### Common terms and phrases

2-satisfiability A-SAT average backtracking benchmark graphs blossom pair boolean branch and bound branching rule clique found Computer Science constraint corresponding Davis-Putnam degree denote density DIMACS DMCLIQUE DSATUR edges efficient exact algorithm experiments Figure flips formula function graph coloring GRASP greedy algorithm greedy heuristic GSAT Hamming graphs Hybrid hyperarc hypergraph implementation improvement increases initial input iterations large cliques largest clique linear literals local search lower bound Mathematics Mathematics Subject Classification maximum clique problem maximum independent set method minimum node cover number of clauses number of variables obtained parameters Pardalos performance phase plateau posiform procedure quadratic Ramsey random graphs randomly ratio relaxation restarts SASAT Satisfiabilitg satisfiability problems Section selection set problem simulated annealing solution solved stable set Step strategy subgraph Table tabu search unit clause unsatisfiable upper bound vertex vertices

### Popular passages

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