@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",

}