Conflict Analysis and Branching Heuristics in the Search for Graph Automorphisms
Paolo Codenotti, Hadi Katebi, Karem A. Sakallah, Igor L. Markov · 2013
We adapt techniques from the constraint programming and satisfiability literatures to expedite the search for graph automorphisms. Specifically, we implement conflict-driven backjumping, several branching heuristics, andrestarts. To support backjumping, we extend high-performance search for graph automorphisms with a novel framework for conflict analysis. Empirically, these techniques improve performance up to several orders of magnitude.