The paper introduces an efficient algorithm for determining subgraph isomorphism, which is a fundamental problem in graph theory and has applications in various fields such as chemistry, scene analysis, and pattern recognition. The algorithm improves upon a brute-force tree-search enumeration procedure by incorporating a refinement procedure that eliminates successor nodes in the tree search, thereby reducing computational time. The refinement procedure works by testing each 1 in the matrix \( M \) to ensure that it satisfies a necessary condition for subgraph isomorphism, and changing any 1 that does not satisfy the condition to 0. This process is repeated until no further changes are made, ensuring that the algorithm finds all possible isomorphisms.
The paper also includes experimental results comparing the new algorithm with other methods, including a comparison with Corneil and Gotlieb's algorithm for subgraph isomorphism, Bron and Kerbosch's algorithm for clique detection, and Berztiss' algorithm for directed graph isomorphism. The experiments show that the new algorithm is efficient for isomorphic random graphs, with a time complexity roughly proportional to \( p_a^3 \), where \( p_a \) is the number of points in the smaller graph. However, for specific classes of graphs, the algorithm may be less efficient compared to other methods.
Additionally, the paper describes a parallel asynchronous logic-in-memory implementation of the refinement procedure, which could potentially allow for very rapid determination of isomorphism. The hardware implementation is designed to exploit the limited parallelism of a digital computer, making it suitable for real-time applications.
The paper concludes by discussing the advantages and limitations of the algorithm, emphasizing its ability to handle undirected subgraph isomorphism, despite potentially slower performance for large graphs. The author also acknowledges the contributions of Dr. B. R. Heap and the referee for their suggestions and comments.The paper introduces an efficient algorithm for determining subgraph isomorphism, which is a fundamental problem in graph theory and has applications in various fields such as chemistry, scene analysis, and pattern recognition. The algorithm improves upon a brute-force tree-search enumeration procedure by incorporating a refinement procedure that eliminates successor nodes in the tree search, thereby reducing computational time. The refinement procedure works by testing each 1 in the matrix \( M \) to ensure that it satisfies a necessary condition for subgraph isomorphism, and changing any 1 that does not satisfy the condition to 0. This process is repeated until no further changes are made, ensuring that the algorithm finds all possible isomorphisms.
The paper also includes experimental results comparing the new algorithm with other methods, including a comparison with Corneil and Gotlieb's algorithm for subgraph isomorphism, Bron and Kerbosch's algorithm for clique detection, and Berztiss' algorithm for directed graph isomorphism. The experiments show that the new algorithm is efficient for isomorphic random graphs, with a time complexity roughly proportional to \( p_a^3 \), where \( p_a \) is the number of points in the smaller graph. However, for specific classes of graphs, the algorithm may be less efficient compared to other methods.
Additionally, the paper describes a parallel asynchronous logic-in-memory implementation of the refinement procedure, which could potentially allow for very rapid determination of isomorphism. The hardware implementation is designed to exploit the limited parallelism of a digital computer, making it suitable for real-time applications.
The paper concludes by discussing the advantages and limitations of the algorithm, emphasizing its ability to handle undirected subgraph isomorphism, despite potentially slower performance for large graphs. The author also acknowledges the contributions of Dr. B. R. Heap and the referee for their suggestions and comments.