Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. (English) Zbl 0864.90118

Fleurent, Charles; Ferland, Jacques A.

Johnson, David S. (ed.) et al., Cliques, coloring, and satisfiability. Second DIMACS implementation challenge. Proceedings of a workshop held at DIMACS, October 11–13, 1993. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 26, 619-652 (1996).

Summary: Using object-oriented design and the C\(^{++}\) programming language, generic operators are developed for tabu search and genetic algorithms. These operators are used for the graph coloring, maximum clique and satisfiability problems. The availability of all methods for each problem allows us to consider hybrid schemes.
For the entire collection see [Zbl 0851.00080].

MSC:

90C35	Programming involving graphs or networks
68R10	Graph theory (including graph drawing) in computer science
90C09	Boolean programming

Keywords:

object-oriented design; tabu search; genetic algorithms; graph coloring; maximum clique; satisfiability