Advanced

Determining the consistency of resolved triplets and fan triplets

Jansson, Jesper LU ; Lingas, Andrzej LU ; Rajaby, Ramesh and Sung, Wing Kin (2017) 21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017 In Research in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings 10229 LNCS. p.82-98
Abstract

The R+−F+− Consistency problem takes as input two sets R+ and R of resolved triplets and two sets F+ and F of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R+ ∪ F+ and no elements in R ∪ F as embedded subtrees, if such a tree exists. This paper presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R = ∅ whose running time is linear in the size of the input and therefore optimal.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Algorithm, Computational complexity, Phylogenetic tree, Rooted triplets consistency
in
Research in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings
volume
10229 LNCS
pages
17 pages
publisher
Springer Verlag
conference name
21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017
external identifiers
  • scopus:85018377352
ISSN
16113349
03029743
ISBN
9783319569697
DOI
10.1007/978-3-319-56970-3_6
language
English
LU publication?
yes
id
051ba956-02f6-492f-ac58-3f8ea988cab0
date added to LUP
2017-05-23 10:15:29
date last changed
2018-01-07 12:04:53
@inproceedings{051ba956-02f6-492f-ac58-3f8ea988cab0,
  abstract     = {<p>The R<sup>+−</sup>F<sup>+−</sup> Consistency problem takes as input two sets R<sup>+</sup> and R<sup>−</sup> of resolved triplets and two sets F<sup>+</sup> and F<sup>−</sup> of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R<sup>+</sup> ∪ F<sup>+</sup> and no elements in R<sup>−</sup> ∪ F<sup>−</sup> as embedded subtrees, if such a tree exists. This paper presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R<sup>−</sup> = ∅ whose running time is linear in the size of the input and therefore optimal.</p>},
  author       = {Jansson, Jesper and Lingas, Andrzej and Rajaby, Ramesh and Sung, Wing Kin},
  booktitle    = {Research in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings},
  isbn         = {9783319569697},
  issn         = {16113349},
  keyword      = {Algorithm,Computational complexity,Phylogenetic tree,Rooted triplets consistency},
  language     = {eng},
  pages        = {82--98},
  publisher    = {Springer Verlag},
  title        = {Determining the consistency of resolved triplets and fan triplets},
  url          = {http://dx.doi.org/10.1007/978-3-319-56970-3_6},
  volume       = {10229 LNCS},
  year         = {2017},
}