@inproceedings{967881149e2c436399e50547463ae930,
title = "Determining the consistency of resolved triplets and fan triplets",
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.",
keywords = "Algorithm, Computational complexity, Phylogenetic tree, Rooted triplets consistency",
author = "Jansson, {Jesper Andreas} and Andrzej Lingas and Ramesh Rajaby and Sung, {Wing Kin}",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-56970-3_6",
language = "English",
isbn = "9783319569697",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "82--98",
booktitle = "Research in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings",
address = "Germany",
note = "21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017 ; Conference date: 03-05-2017 Through 07-05-2017",
}