2010/03/01 by J. R. Ullmann · 2 citations
Computer Science · Mathematics · #Constraint Satisfaction and Optimization #Data Management and Algorithms #Advanced Database Systems and Queries #Constraint satisfaction problem #Binary search algorithm #Algorithm #Subgraph isomorphism problem #Search algorithm #Domain (mathematical analysis) #Computer science #Constraint satisfaction #Matching (statistics) #Theoretical computer science #Mathematics #Artificial intelligence
paper · pdf · doi:10.1145/1671970.1921702
openalex publication_date 2010/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
A solution to a binary constraint satisfaction problem is a set of discrete values, one in each of a given set of domains, subject to constraints that allow only prescribed pairs of values in specified pairs of domains. Solutions are sought by backtrack search interleaved with a process that removes from domains those values that are currently inconsistent with provisional choices already made in the course of search. For each value in a given domain, a bit-vector shows which values in another domain are or are not permitted in a solution. Bit-vector representation of constraints allows bit-parallel, therefore fast, operations for editing domains during search. This article revises and updates bit-vector algorithms published in the 1970's, and introduces focus search, which is a new bit-vector algorithm relying more on search and less on domain-editing than previous algorithms. Focus search is competitive within a limited family of constraint satisfaction problems. Determination of subgraph isomorphism is a specialized binary constraint satisfaction problem for which bit-vector algorithms have been widely used since the 1980s, particularly for matching molecular structures. This article very substantially updates the author's 1976 subgraph isomorphism algorithm, and reports experimental results with random and real-life data.