Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Cliques, Coloring, and Satisfiability
 
Edited by: David S. Johnson A T & T Bell Laboratories, Murray Hill, NJ
Michael A. Trick Carnegie Mellon University, Pittsburgh, PA
A co-publication of the AMS and DIMACS
Cliques, Coloring, and Satisfiability
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
Cliques, Coloring, and Satisfiability
Click above image for expanded view
Cliques, Coloring, and Satisfiability
Edited by: David S. Johnson A T & T Bell Laboratories, Murray Hill, NJ
Michael A. Trick Carnegie Mellon University, Pittsburgh, PA
A co-publication of the AMS and DIMACS
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 Details
     
     
    DIMACS - Series in Discrete Mathematics and Theoretical Computer Science
    Volume: 261996; 657 pp
    MSC: 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).

    Readership

    Graduate 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
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 261996; 657 pp
MSC: 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).

Readership

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
Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.