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.2018.54
URN: urn:nbn:de:0030-drops-96367
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9636/
Go to the corresponding LIPIcs Volume Portal

Droschinsky, Andre ; Kriege, Nils M. ; Mutzel, Petra

Largest Weight Common Subtree Embeddings with Distance Penalties

pdf-format:
LIPIcs-MFCS-2018-54.pdf (0.5 MB)

Abstract

The largest common embeddable subtree problem asks for the largest possible tree embeddable into two input trees and generalizes the classical maximum common subtree problem. Several variants of the problem in labeled and unlabeled rooted trees have been studied, e.g., for the comparison of evolutionary trees. We consider a generalization, where the sought embedding is maximal with regard to a weight function on pairs of labels. We support rooted and unrooted trees with vertex and edge labels as well as distance penalties for skipping vertices. This variant is important for many applications such as the comparison of chemical structures and evolutionary trees. Our algorithm computes the solution from a series of bipartite matching instances, which are solved efficiently by exploiting their structural relation and imbalance. Our analysis shows that our approach improves or matches the running time of the formally best algorithms for several problem variants. Specifically, we obtain a running time of O(|T| |T'|Delta) for two rooted or unrooted trees T and T', where Delta=min{Delta(T),Delta(T')} with Delta(X) the maximum degree of X. If the weights are integral and at most C, we obtain a running time of O(|T| |T'|sqrt Delta log (C min{|T|,|T'|})) for rooted trees.

BibTeX - Entry

@InProceedings{droschinsky_et_al:LIPIcs:2018:9636,
  author =	{Andre Droschinsky and Nils M. Kriege and Petra Mutzel},
  title =	{{Largest Weight Common Subtree Embeddings with Distance Penalties}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9636},
  URN =		{urn:nbn:de:0030-drops-96367},
  doi =		{10.4230/LIPIcs.MFCS.2018.54},
  annote =	{Keywords: maximum common subtree, largest embeddable subtree, topological embedding, maximum weight matching, subtree homeomorphism}
}

Keywords: maximum common subtree, largest embeddable subtree, topological embedding, maximum weight matching, subtree homeomorphism
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI