Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time
Loading...
Authors
Author (Corporation)
Publication date
2014
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editors
El Gayar, Neamat
Schwenker, Friedhelm
Suen, Cheng
Editor (Corporation)
Supervisor
Parent work
Artificial Neural Networks in Pattern Recognition - 6th IAPR TC 3 International Workshop, ANNPR 2014, Montreal, QC, Canada, October 6-8, 2014. Proceedings
Special issue
DOI of the original publication
Link
Series
Lecture Notes in Computer Science
Series number
8774
Volume
Issue / Number
Pages / Duration
129-140
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Hamburg
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
Exact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local – rather than the global – structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.
Keywords
Subject (DDC)
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
978-3-319-11655-6
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
License
Citation
Riesen, K., Fischer, A., & Bunke, H. (2014). Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time. In N. El Gayar, F. Schwenker, & C. Suen (Eds.), Artificial Neural Networks in Pattern Recognition - 6th IAPR TC 3 International Workshop, ANNPR 2014, Montreal, QC, Canada, October 6-8, 2014. Proceedings (pp. 129–140). Springer. http://hdl.handle.net/11654/8222