1 Search Results for "van der Ster, Suzanne"


Document
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest

Authors: Frans Schalekamp, Anke van Zuylen, and Suzanne van der Ster

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the Subtree Prune-and-Regraft (SPR) distance between two phylogenetic trees. Our result improves on the very recent 2.5-approximation algorithm due to Shi, Feng, You and Wang (2015). Our algorithm is the first approximation algorithm for this problem that uses LP duality in its analysis.

Cite as

Frans Schalekamp, Anke van Zuylen, and Suzanne van der Ster. A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{schalekamp_et_al:LIPIcs.ICALP.2016.70,
  author =	{Schalekamp, Frans and van Zuylen, Anke and van der Ster, Suzanne},
  title =	{{A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.70},
  URN =		{urn:nbn:de:0030-drops-62149},
  doi =		{10.4230/LIPIcs.ICALP.2016.70},
  annote =	{Keywords: Maximum agreement forest, phylogenetic tree, SPR distance, subtree prune-and-regraft distance, computational biology}
}
  • Refine by Author
  • 1 Schalekamp, Frans
  • 1 van Zuylen, Anke
  • 1 van der Ster, Suzanne

  • Refine by Classification

  • Refine by Keyword
  • 1 Maximum agreement forest
  • 1 SPR distance
  • 1 computational biology
  • 1 phylogenetic tree
  • 1 subtree prune-and-regraft distance

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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