
eBook ISBN: | 978-1-4704-3984-2 |
Product Code: | DIMACS/26.E |
List Price: | $138.00 |
MAA Member Price: | $124.20 |
AMS Member Price: | $110.40 |

eBook ISBN: | 978-1-4704-3984-2 |
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.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published 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 0-1 algorithm for the stable set problem
-
Camouflaging independent sets in quasi-random 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 polynomial-time 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 k-colorable 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 2-SAT
-
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 Davis-Putnam algorithms for maximum satisfiability problems
-
Combination
-
Object-oriented 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.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published 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 0-1 algorithm for the stable set problem
-
Camouflaging independent sets in quasi-random 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 polynomial-time 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 k-colorable 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 2-SAT
-
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 Davis-Putnam algorithms for maximum satisfiability problems
-
Combination
-
Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability
-
Appendix. Second DIMACS challenge test problems