2 Search Results for "Bordewich, Magnus"


Document
An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions

Authors: Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)


Abstract
In the NP-hard Longest Common Subsequence problem (LCS), given a set of strings, the task is to find a string that can be obtained from every input string using as few deletions as possible. LCS is one of the most fundamental string problems with numerous applications in various areas, having gained a lot of attention in the algorithms and complexity research community. Significantly improving on an algorithm by Irving and Fraser [CPM'92], featured as a research challenge in a 2014 survey paper, we show that LCS is fixed-parameter tractable (FPT) when parameterized by the maximum number of deletions per input string. Given the relatively moderate running time of our algorithm (linear time when the parameter is a constant) and small parameter values to be expected in several applications, we believe that our purely theoretical analysis could finally pave the way to a new, exact and practically useful algorithm for this notoriously hard string problem.

Cite as

Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau. An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2022.6,
  author =	{Bulteau, Laurent and Jones, Mark and Niedermeier, Rolf and Tantau, Till},
  title =	{{An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.6},
  URN =		{urn:nbn:de:0030-drops-161338},
  doi =		{10.4230/LIPIcs.CPM.2022.6},
  annote =	{Keywords: NP-hard string problems, multiple sequence alignment, center string, parameterized complexity, search tree algorithms, enumerative algorithms}
}
Document
Algorithms and Complexity in Phylogenetics (Dagstuhl Seminar 19443)

Authors: Magnus Bordewich, Britta Dorn, Simone Linz, and Rolf Niedermeier

Published in: Dagstuhl Reports, Volume 9, Issue 10 (2020)


Abstract
Phylogenetics is the study of ancestral relationships between species. Its central goal is the reconstruction and analysis of phylogenetic trees and networks. Even though research in phylogenetics is motivated by biological questions and applications, it heavily relies on mathematics and computer science. Dagstuhl Seminar 19443 on Algorithms and Complexity in Phylogenetics aimed at bringing together researchers from phylogenetics and theoretical computer science to enable an exchange of expertise, facilitate interactions across both research areas, and establish new collaborations. This report documents the program and outcomes of the seminar. It contains an executive summary, abstracts of talks, short summaries of working groups, and a list of open problems that were posed during the seminar.

Cite as

Magnus Bordewich, Britta Dorn, Simone Linz, and Rolf Niedermeier. Algorithms and Complexity in Phylogenetics (Dagstuhl Seminar 19443). In Dagstuhl Reports, Volume 9, Issue 10, pp. 134-151, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@Article{bordewich_et_al:DagRep.9.10.134,
  author =	{Bordewich, Magnus and Dorn, Britta and Linz, Simone and Niedermeier, Rolf},
  title =	{{Algorithms and Complexity in Phylogenetics (Dagstuhl Seminar 19443)}},
  pages =	{134--151},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2020},
  volume =	{9},
  number =	{10},
  editor =	{Bordewich, Magnus and Dorn, Britta and Linz, Simone and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.10.134},
  URN =		{urn:nbn:de:0030-drops-118590},
  doi =		{10.4230/DagRep.9.10.134},
  annote =	{Keywords: Approximation algorithms, Evolution, Parameterized algorithms, Phylogenetic trees and networks}
}
  • Refine by Author
  • 2 Niedermeier, Rolf
  • 1 Bordewich, Magnus
  • 1 Bulteau, Laurent
  • 1 Dorn, Britta
  • 1 Jones, Mark
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Theory and algorithms for application domains

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 Evolution
  • 1 NP-hard string problems
  • 1 Parameterized algorithms
  • 1 Phylogenetic trees and networks
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

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