A Parallel, Backjumping Subgraph Isomorphism Algorithm using Supplemental Graphs

Revision: 
1
Contributing Authors: 
  • Ciaran McCreesh
  • Patrick Prosser
Description: 

The subgraph isomorphism problem involves finding a pattern graph inside a target graph. We present a new bit- and thread-parallel constraint-based search algorithm for the problem, and experiment on a wide range of standard benchmark instances to demonstrate its effectiveness. We introduce supplemental graphs, to create implied constraints. We use a new low-overhead, lazy variation of conflict directed backjumping which interacts safely with parallel search, and a counting-based all-different propagator which is better suited for large domains.

Instructions: 
Box Type: