Abstract
Recently, the concept of ordered graphs has been introduced and it was shown that isomorphism of ordered graphs can be solved in quadratic time. In the present paper we consider a special case of the subgraph isomorphism problem for ordered graphs, called marked subgraph isomorphism. An algorithm of O(m 1 m 2) complexity is developed for finding all marked subgraph isomorphisms from a graph G 1 to another graph G 2, where m 1 and m 2 are the number of edges in G 1 and G 2, respectively. We demonstrate the usefulness of our algorithm by applying it to solving the subcircuit extraction problem. It turns out that our approach is much more efficient than traditional methods based on general subgraph isomorphism techniques.
Chapter PDF
References
P. Dublish, Some comments on the subtree isomorphism problem for ordered trees, Information Processing Letters, 36: 273–275, 1990.
M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman and Co., 1979.
J.E. Hopcroft and J.K. Wong, Linear time algorithm for isomorphism of planar graphs, Proc. of 6th Annual ACM Symposium on Theory of Computing, 172–184, 1974.
X. Jiang and H. Bunke, A simple and efficient algorithm for determining the symmetries of polyhedra, Graphical Models and Image Processing, 54(1):91–95, 1992.
X. Jiang, K. Yu, and H. Bunke, Detection of rotational and involutational symmetries and congruity of polyhedra, The Visual Computer, 12(4): 193–201, 1996.
X. Jiang and H. Bunke, Including geometry in graph representations: A quadratictime graph isomorphism algorithm and its applications, In Advances in Structural and Syntactical Pattern Recognition (P. Perner, P. Wang, A. Rosenfeld, Eds.), Lectures Notes in Computer Science 1121, Springer-Verlag, 110–119, 1996.
X. Jiang and H. Bunke, On the coding of ordered graphs, Computing, 1998. (to appear)
S. Kasif, L. Kitchen, and A. Rosenfeld, A Hough transform technique for subgraph isomorphism, Pattern Recognition Letters, 2: 83–88, 1983.
E.M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Science, 25: 42–65, 1982.
M. Ohlrich et al., SubGemini: Identifying subcircuits using a fast subgraph isomorphism algorithm, Proc. of 30th ACM1IEEE Design Automation Conference, 31–37, 1993.
N. Vijaykrishnan and N. Ranganathan, SUBGEN: A genetic approach for subcircuit extraction, Proc. of Int. Conf. on VLSI Design, Bangalore, 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jiang, X., Bunke, H. (1998). Marked subgraph isomorphism of ordered graphs. In: Amin, A., Dori, D., Pudil, P., Freeman, H. (eds) Advances in Pattern Recognition. SSPR /SPR 1998. Lecture Notes in Computer Science, vol 1451. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0033230
Download citation
DOI: https://doi.org/10.1007/BFb0033230
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64858-1
Online ISBN: 978-3-540-68526-5
eBook Packages: Springer Book Archive
