Thumbnail
Access Restriction
Subscribed

Author Ullmann, Julian R.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword AllDifferent constraint ♦ Backtrack ♦ Binary constraints ♦ Bit-vector ♦ Constraint propagation ♦ Constraint satisfaction ♦ Domain reduction ♦ Focus search ♦ Forward checking ♦ Graph indexing ♦ Molecule matching ♦ Prematching ♦ Signature file ♦ Subgraph isomorphism
Abstract 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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-02-07
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 15
Page Count 64
Starting Page 1.1
Ending Page 1.64


Open content in new tab

   Open content in new tab
Source: ACM Digital Library