Please use this identifier to cite or link to this item:
|Title:||Non-shared edges and nearest neighbor interchanges revisited||Authors:||Hon, W.-K.
Non-shared edge distance
|Issue Date:||2004||Citation:||Hon, W.-K., Kao, M.-Y., Lam, T.-W., Sung, W.-K., Yiu, S.-M. (2004). Non-shared edges and nearest neighbor interchanges revisited. Information Processing Letters 91 (3) : 129-134. ScholarBank@NUS Repository. https://doi.org/10.1016/j.ipl.2004.04.003||Abstract:||The number of non-shared edges of two phylogenies is a basic measure of the dissimilarity between the phylogenies. The non-shared edge distance is also a building block for approximating a more sophisticated measure called the nearest neighbor interchange (NNI) distance. In this paper, we give the first sub-quadratic time algorithm for computing the non-shared edge distance, whose running time is O(nlogn). Based on this result, we can speed up the existing approximation algorithm for the NNI distance from O(n2) time to O(nlogn) time. © 2004 Elsevier B.V. All rights reserved.||Source Title:||Information Processing Letters||URI:||http://scholarbank.nus.edu.sg/handle/10635/39214||ISSN:||00200190||DOI:||10.1016/j.ipl.2004.04.003|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.