DocumentCode
680765
Title
Conflict Analysis and Branching Heuristics in the Search for Graph Automorphisms
Author
Codenotti, Paolo ; Katebi, Hadi ; Sakallah, Karem A. ; Markov, Igor L.
Author_Institution
EECS Dept., Univ. of Michigan, Ann Arbor, MI, USA
fYear
2013
fDate
4-6 Nov. 2013
Firstpage
907
Lastpage
914
Abstract
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.
Keywords
computability; constraint handling; graph theory; search problems; andrestarts; branching heuristics; conflict analysis; conflict-driven backjumping; constraint programming; graph automorphisms; high-performance search; satisfiability; Algorithm design and analysis; Benchmark testing; Generators; Labeling; Orbits; Partitioning algorithms; Software algorithms;
fLanguage
English
Publisher
ieee
Conference_Titel
Tools with Artificial Intelligence (ICTAI), 2013 IEEE 25th International Conference on
Conference_Location
Herndon, VA
ISSN
1082-3409
Print_ISBN
978-1-4799-2971-9
Type
conf
DOI
10.1109/ICTAI.2013.139
Filename
6735350
Link To Document