Relational consistency algorithms and their application in finding subgraph and graph isomorphisms

DOI10.1016/0020-0255(79)90023-9zbMath0442.68065OpenAlexW2022739485MaRDI QIDQ1143807

J. J. McGregor

Publication date: 1979

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(79)90023-9

zbMATH Keywords

tree search algorithmsdetermination of subgraph and graph isomorphismspath consistency algorithmsrelational consistency algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

Binary vs. non-binary constraints ⋮ Partitioning graph matching with constraints ⋮ Partition search for non-binary constraint satisfaction ⋮ Theoretical analysis of singleton arc consistency and its extensions ⋮ No more ``Partial and ``Full Looking Ahead ⋮ A theoretical evaluation of selected backtracking algorithms. ⋮ Path Consistency by Dual Consistency ⋮ A logic language for combinatorial optimization ⋮ An optimal coarse-grained arc consistency algorithm ⋮ AllDifferent-based filtering for subgraph isomorphism ⋮ Forward checking and intelligent backtracking ⋮ A parametric filtering algorithm for the graph isomorphism problem ⋮ Degree Reduction in Labeled Graph Retrieval ⋮ Propagation engine prototyping with a domain specific language ⋮ Backjump-based backtracking for constraint satisfaction problems

Cites Work

• Consistency in networks of relations
• Networks of constraints: Fundamental properties and applications to picture processing
• An Algorithm for Subgraph Isomorphism
• Scene Labeling by Relaxation Operations
• A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words
• A Proof Procedure Using Connection Graphs
• THE CHARACTERIZATION OF BINARY RELATION HOMOMORPHISMS
• A new type of computer for problems in propositional logic, with greatly reduced scanning procedures
• An Efficient Algorithm for Graph Isomorphism
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relational consistency algorithms and their application in finding subgraph and graph isomorphisms