DSpace at School of Computing, NUS: Item 1900.100/2824

Please use this identifier to cite or link to this item: http://hdl.handle.net/1900.100/2824

Title:	Edit Distance Evaluation on Graph Structures
Authors:	ZENG, Zhiping TUNG, Anthony K.H. WANG, Jianyong ZHOU, Lizhu
Issue Date:	19-Jun-2008
Series/Report no.:	;TRA6/08
Abstract:	Graph data has became ubiquitous and manipulating them based on similarity is essential for many applications. Graph edit distance is one of the most widely accepted measure to determine similarities between graphs and has extensive applications in the fields of pattern recognition, computer vision etc. Unfortunately, the problem of graph edit dis- tance computation is NP-Hard in general and is unlikely to be approximated within a polynomial time computable fac- tor f(n) in polynomial time. Accordingly, in this paper we introduce three novel methods to compute the upper and lower bounds for the edit distance between two graphs in polynomial time. Applying these methods, three algorithms AppFull, ExactSub and AppSub are introduced to per- form different kinds of graph search on graph databases. Comprehensive experimental studies are conducted on both real and synthetic datasets to examine various aspects of the methods for bounding graph edit distance. Result shows that these methods .....
URI:	http://hdl.handle.net/1900.100/2824
Appears in Collections:	Technical Reports

Files in This Item:

File	Size	Format
TRA6-08.pdf	337Kb	Adobe PDF	View/Open