License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.33
URN: urn:nbn:de:0030-drops-64475
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6447/
Droschinsky, Andre ;
Kriege, Nils M. ;
Mutzel, Petra
Faster Algorithms for the Maximum Common Subtree Isomorphism Problem
Abstract
The maximum common subtree isomorphism problem asks for the largest possible isomorphism between subtrees of two given input trees. This problem is a natural restriction of the maximum common subgraph problem, which is NP-hard in general graphs. Confining to trees renders polynomial time algorithms possible and is of fundamental importance for approaches on more general graph classes.Various variants of this problem in trees have been intensively studied. We consider the general case, where trees are neither rooted nor ordered and the isomorphism is maximum w.r.t. a weight function on the mapped vertices and edges. For trees of order n and maximum degree Delta our algorithm achieves a running time of O(n^2*Delta) by exploiting the structure of the matching instances arising as subproblems. Thus our algorithm outperforms the best previously known approaches. No faster algorithm is possible for trees of bounded degree and for trees of unbounded degree we show that a further reduction of the running time would directly improve the best known approach to the assignment problem. Combining a polynomial-delay algorithm for the enumeration of all maximum common subtree isomorphisms with central ideas of our new algorithm leads to an improvement of its running time from O(n^6+T*n^2) to O(n^3+T*n*Delta), where n is the order of the larger tree, T is the number of different solutions, and Delta is the minimum of the maximum degrees of the input trees. Our theoretical results are supplemented by an experimental evaluation on synthetic and real-world instances.
BibTeX - Entry
@InProceedings{droschinsky_et_al:LIPIcs:2016:6447,
author = {Andre Droschinsky and Nils M. Kriege and Petra Mutzel},
title = {{Faster Algorithms for the Maximum Common Subtree Isomorphism Problem}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {33:1--33:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6447},
URN = {urn:nbn:de:0030-drops-64475},
doi = {10.4230/LIPIcs.MFCS.2016.33},
annote = {Keywords: MCS, maximum common subtree, enumeration algorithms, maximum weight bipartite matchings}
}
|
Keywords: |
|
MCS, maximum common subtree, enumeration algorithms, maximum weight bipartite matchings |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
