AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Cliques, Coloring, and Satisfiability
About this Title
David Stifler Johnson, A T & T Bell Laboratories, Murray Hill, NJ and Michael A. Trick, Carnegie Mellon University, Pittsburgh, PA, Editors
Publication: DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Publication Year:
1996; Volume 26
ISBNs: 978-0-8218-6609-2 (print); 978-1-4704-3984-2 (online)
DOI: https://doi.org/10.1090/dimacs/026
MathSciNet review: MR1423138
MSC: Primary 68-06; Secondary 90-06
ReadershipTable of Contents
Front/Back Matter
Chapters
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