J. R. Ullmann
Abstract
Subgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess the time actually taken by the new algorithm, subgraph isomorphism, clique detection, graph isomorphism, and directed graph isomorphism experiments have been carried out with random and with various nonrandom graphs.
A parallel asynchronous logic-in-memory implementation of a vital part of the algorithm is also described, although this hardware has not actually been built. The hardware implementation would allow very rapid determination of isomorphism.
- 1 BARROW, H. G , AMBLER, A. P, AND BURSTALL, R.M. Some techniques for recogmsing structures in pictures. In Frontzers of Pattern Recogn, tzon, S. Watanabe, Ed., Academic Press, New York, 1972, pp. 1-29Google Scholar
Cross Ref
- 2 BERZTISS, A. T. A backtrack procedure for isomorphism of directed graphs. J. ACM gO, 3 (July 1973), 365-377. Google ScholarDigital Library
- 3 BRON, C, AND KERBOSCH, J Algorithm 457. Finding all chques in an undirected graph {H} Comm. ACM 16, 9 (Sept. 1973), 575-577 Google ScholarDigital Library
- 4 CORNEIL, D. G, AND GOTLIEB, C C. An efficient algomthm for graph isomorphism J. ACM 17, 1 (Jan 1970), 51-64. Google ScholarDigital Library
- 5 HARARY, F Graph Theory. Addison-Wesley, Reading, Mass, 1969.Google ScholarCross Ref
- 6 I,EVITT, K. N., AND KAUTZ, W. H Cellular arrays for the solution of graph problems Comm. ACM 15, 9 (Sept 1972), 789-801 Google ScholarDigital Library
- 7 NILSSON, N. J. Problem-Solvzng Methods zn Artzficzal intellzgence. McGraw-Hill, New York, 1971 Google ScholarDigital Library
- 8 OSTEEN, R. E., AND TOU, J.T. Achque-detectlon algorithm based on neighbourhoods in graphs. lnt J of Comput and Inform Sczs g, 4 (Dec. 1973), 257-268.Google Scholar
- 9 PIKE, M C, AND HILL, I.D. Algomthm 266: Pseudo-random numbers {GS}. Comm. ACM 8, 10 (Oct 1965), 605-606 Google ScholarDigital Library
- 10 SAKAr, T., NAGAO, M., AND MATSUSHIMA, H. Extraction of invariant picture substructures by computer. Comput Graphzcs and Image Process 1, 1 (April 1972), 81-96.Google ScholarCross Ref
- 11 ULL~ANN;-J. R Pattern Recogn~tzon Teehnzques. Butterworths, London, and Crane Russak, New York, 1973.Google Scholar
Index Terms
- An Algorithm for Subgraph Isomorphism
Recommendations
The subgraph isomorphism problem for outerplanar graphs
This paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity ...
Induced subgraph isomorphism
The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced ...
Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs
Given two graphs G and H as input, the Induced Subgraph Isomorphism (ISI) problem is to decide whether G has an induced subgraph that is isomorphic to H. This problem is NP-complete already when G and H are restricted to disjoint unions of paths, and ...
Comments