An Algorithm for Subgraph Isomorphism

An Algorithm for Subgraph Isomorphism

January 1976 | J. R. ULLMANN
This paper presents an efficient algorithm for subgraph isomorphism, which improves upon brute-force tree-search methods by eliminating unnecessary successor nodes during the search. The algorithm is designed to determine whether a given graph is isomorphic to a subgraph of another graph, and it has been tested on both random and nonrandom graphs. The algorithm also includes a refinement procedure that reduces the number of 1's in the matrix used to represent the isomorphism, thereby reducing the search space and improving efficiency. The algorithm is based on a matrix representation of the graphs, where each element of the matrix indicates whether a point in one graph corresponds to a point in another. The refinement procedure checks whether each 1 in the matrix satisfies a certain condition, and if not, it changes the 1 to a 0. This process is repeated until no further changes are needed, ensuring that only valid isomorphisms are considered. The algorithm has been tested on various types of graphs, including cliques, graph isomorphism, and directed graph isomorphism. The results show that the algorithm is significantly faster than brute-force methods, especially for large graphs. The algorithm also includes a parallel hardware implementation that could allow for very rapid determination of isomorphism. The paper also discusses the use of Boolean matrices and the formulation of the refinement procedure in terms of Boolean operations. The algorithm is described in detail, including the steps involved in the refinement process and the conditions under which the algorithm terminates. The paper concludes that the algorithm is efficient for isomorphic random graphs, although it may be less efficient for certain types of graphs. The algorithm is particularly effective for undirected subgraph isomorphism, although it can be slow for large graphs.This paper presents an efficient algorithm for subgraph isomorphism, which improves upon brute-force tree-search methods by eliminating unnecessary successor nodes during the search. The algorithm is designed to determine whether a given graph is isomorphic to a subgraph of another graph, and it has been tested on both random and nonrandom graphs. The algorithm also includes a refinement procedure that reduces the number of 1's in the matrix used to represent the isomorphism, thereby reducing the search space and improving efficiency. The algorithm is based on a matrix representation of the graphs, where each element of the matrix indicates whether a point in one graph corresponds to a point in another. The refinement procedure checks whether each 1 in the matrix satisfies a certain condition, and if not, it changes the 1 to a 0. This process is repeated until no further changes are needed, ensuring that only valid isomorphisms are considered. The algorithm has been tested on various types of graphs, including cliques, graph isomorphism, and directed graph isomorphism. The results show that the algorithm is significantly faster than brute-force methods, especially for large graphs. The algorithm also includes a parallel hardware implementation that could allow for very rapid determination of isomorphism. The paper also discusses the use of Boolean matrices and the formulation of the refinement procedure in terms of Boolean operations. The algorithm is described in detail, including the steps involved in the refinement process and the conditions under which the algorithm terminates. The paper concludes that the algorithm is efficient for isomorphic random graphs, although it may be less efficient for certain types of graphs. The algorithm is particularly effective for undirected subgraph isomorphism, although it can be slow for large graphs.
Reach us at info@study.space
Understanding An Algorithm for Subgraph Isomorphism