Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism

DOI10.1145/1671970.1921702MaRDI QIDQ5406228zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Julian R. Ullmann

Publication date 1 April 2014

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1671970.1921702

zbMATH Keywords

AllDifferent constraintbacktrackbinary constraintsbit-vectorconstraint propagationconstraint satisfactiondomain reductionfocus searchforward checkinggraph indexingmolecule matchingprematchingsignature filesubgraph isomorphism

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• scientific article; zbMATH DE number 2243409
• Sharpening constraint programming approaches for bit-vector theory
• An alternative to SAT-based approaches for bit-vectors
• New schemes for simplifying binary constraint satisfaction problems
• Towards satisfiability modulo parametric bit-vectors
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems
• Efficiently solving quantified bit-vector formulas
• Solving subgraph isomorphism problems with constraint programming
• Sparsification of Binary CSPs

Cited in

(9)

• An algorithm for weighted sub-graph matching based on gradient flows
• A long trip in the charming world of graphs for pattern recognition
• Efficient subgraph matching using topological node feature constraints
• VF2++ -- an improved subgraph isomorphism algorithm
• Sharpening constraint programming approaches for bit-vector theory
• A new branch-and-filter exact algorithm for binary constraint satisfaction problems
• Constraint satisfaction through GBP-guided deliberate bit flipping
• Degree reduction in labeled graph retrieval
• The secret life of keys: on the calculation of mechanical lock systems

This page was built for publication: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5406228)