Hybrid symbolic-explicit techniques for the graph coloring problem
Silvia Chiusano, Fulvio Corno, P. Prinetto, Matteo Sonza Reorda · 1997
This paper presents an algorithmic technique based on hybridizing Symbolic Manipulation Techniques based on BDDs with more traditional Explicit solving algorithms. To validate the approach, the graph coloring problem has been selected as a hard-to-solve problem, and an optimized solution based on hybrid techniques has been implemented. Experimental results on a set of benchmarks derived from the CAD for VLSI area show the applicability of the approach to graphs with millions of vertices in a limited CPU time. 1.