@inproceedings{c4a69186343d438fa61c469f92ed3888,
title = "An efficient algorithm for the rooted triplet distance between galled trees",
abstract = "The previously fastest algorithm for computing the rooted triplet distance between two input galled trees (i.e., phylogenetic networks whose cycles are vertex-disjoint) runs in O(n2.687) time, where n is the cardinality of the leaf label set. Here, we present an O(n log n)-time solution. Our strategy is to transform the input so that the answer can be obtained by applying an existing O(n log n)-time algorithm for the simpler case of two phylogenetic trees a constant number of times.",
keywords = "Algorithm, Computational complexity, Galled tree, Phylogenetic network comparison, Rooted triplet",
author = "Jansson, {Jesper Andreas} and Ramesh Rajaby and Sung, {Wing Kin}",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-58163-7_8",
language = "English",
isbn = "9783319581620",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "115--126",
booktitle = "Algorithms for Computational Biology - 4th International Conference, AlCoB 2017, Proceedings",
address = "Germany",
note = "4th International Conference on Algorithms for Computational Biology, AlCoB 2017 ; Conference date: 05-06-2017 Through 06-06-2017",
}