| An Algorithm for Subgraph Isomorphism |
| Full text |
 Pdf
(763 KB)
|
| Source
|
Journal of the ACM (JACM)
archive
Volume 23 , Issue 1 (January 1976)
table of contents
Pages: 31 - 42
Year of Publication: 1976
ISSN:0004-5411
|
|
Author
|
|
J. R. Ullmann
|
Division of Computer Science, National Physical Laboratory, Teddington, Middlesex, TW11 OLW, England
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 178, Downloads (12 Months): 1196, Citation Count: 65
|
|
|
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
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-29
|
 |
2
|
|
| |
3
|
|
| |
4
|
|
| |
5
|
HARARY, F Graph Theory. Addison-Wesley, Reading, Mass, 1969.
|
| |
6
|
|
| |
7
|
|
| |
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.
|
| |
9
|
|
| |
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.
|
| |
11
|
ULL~ANN;-J. R Pattern Recogn~tzon Teehnzques. Butterworths, London, and Crane Russak, New York, 1973.
|
CITED BY 65
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alberto Ceselli , Ernesto Damiani , Sabrina De Capitani Di Vimercati , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Modeling and assessing inference exposure in encrypted databases, ACM Transactions on Information and System Security (TISSEC), v.8 n.1, p.119-152, February 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Liping Wang , Qing Li , Na Li , Guozhu Dong , Yu Yang, Substructure similarity measurement in chinese recipes, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
|
|
|
|
|
|
|
|
|
|
|
|
Nathan Clark , Amir Hormati , Scott Mahlke , Sami Yehia, Scalable subgraph mapping for acyclic computation accelerators, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
|
|
|
|
|
|
Chao Liu , Chen Chen , Jiawei Han , Philip S. Yu, GPLAG: detection of software plagiarism by program dependence graph analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
G.2