Search Results

Documents authored by Kriege, Nils M.

Found 2 Possible Name Variants:

Kriege, Nils M.

Document
DOI: 10.4230/LIPIcs.MFCS.2018.54
Largest Weight Common Subtree Embeddings with Distance Penalties

Authors: Andre Droschinsky, Nils M. Kriege, and Petra Mutzel

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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.
Cite as

Andre Droschinsky, Nils M. Kriege, and Petra Mutzel. Largest Weight Common Subtree Embeddings with Distance Penalties. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{droschinsky_et_al:LIPIcs.MFCS.2018.54,
  author =	{Droschinsky, Andre and Kriege, Nils M. and Mutzel, Petra},
  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 =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.54},
  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}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.33
Faster Algorithms for the Maximum Common Subtree Isomorphism Problem

Authors: Andre Droschinsky, Nils M. Kriege, and Petra Mutzel

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

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.
Cite as

Andre Droschinsky, Nils M. Kriege, and Petra Mutzel. Faster Algorithms for the Maximum Common Subtree Isomorphism Problem. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{droschinsky_et_al:LIPIcs.MFCS.2016.33,
  author =	{Droschinsky, Andre and Kriege, Nils M. and Mutzel, Petra},
  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 =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.33},
  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}
}

Kriege, Nils

Document
DOI: 10.4230/OASIcs.GCB.2012.82
Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs

Authors: Marianna D'Addario, Nils Kriege, and Sven Rahmann

Published in: OASIcs, Volume 26, German Conference on Bioinformatics 2012

Abstract
DNA nanoarchitechtures require carefully designed oligonucleotides with certain non-hybridization guarantees, which can be formalized as the q-uniqueness property on the sequence level. We study the optimization problem of finding a longest q-unique DNA sequence. We first present a convenient formulation as an integer linear program on the underlying De Bruijn graph that allows to flexibly incorporate a variety of constraints; solution times for practically relevant values of q are short. We then provide additional insights into the problem structure using the quotient graph of the De Bruijn graph with respect to the equivalence relation induced by reverse complementarity. Specifically, for odd q the quotient graph is Eulerian, so finding a longest q-unique sequence is equivalent to finding an Euler tour and solved in linear time with respect to the output string length. For even q, self-complementary edges complicate the problem, and the graph has to be Eulerized by deleting a minimum number of edges. Two sub-cases arise, for one of which we present a complete solution, while the other one remains open.
Cite as

Marianna D'Addario, Nils Kriege, and Sven Rahmann. Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs. In German Conference on Bioinformatics 2012. Open Access Series in Informatics (OASIcs), Volume 26, pp. 82-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{daddario_et_al:OASIcs.GCB.2012.82,
  author =	{D'Addario, Marianna and Kriege, Nils and Rahmann, Sven},
  title =	{{Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs}},
  booktitle =	{German Conference on Bioinformatics 2012},
  pages =	{82--92},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-44-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{26},
  editor =	{B\"{o}cker, Sebastian and Hufsky, Franziska and Scheubert, Kerstin and Schleicher, Jana and Schuster, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.GCB.2012.82},
  URN =		{urn:nbn:de:0030-drops-37200},
  doi =		{10.4230/OASIcs.GCB.2012.82},
  annote =	{Keywords: DNA sequence design, De Bruijn graph, quotient graph, reverse complement, Euler graph, Euler tour}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact