Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
A generalization of the most common subgraph distance and its application to graph editing
MichaelHecht
Download
PREPRINT 17-040:
[ Publishers's page ]
[ Publishers's page ]
Status: Published
Pattern Recognition Letters 47: 71-78 (2017)
Abstract
We relate the graph editing distance to a generalized weighted version of the most common subgraph distance. To do so, we introduce the new concepts of isotonic shifts and vector weighted graphs. As a consequence we can give a weak but sufficient condition on cost models to result in an edit metric, ensuring the richness of the class of these functions. Moreover, for arbitrary instances we are able to determine a within cubic time computable upper bound on the edit distance, which equals the minimized distance for infinitely many instances.
Keywords
Graph editing, Most common subgraph problem, Tree editing, Sequence alignment, Edit distance