[{"month":"05","_id":"11679","status":"public","language":[{}],"date_created":"2022-07-27T15:02:28Z","publication_status":"published","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"1999-05-01T00:00:00Z","quality_controlled":"1","type":"journal_article","oa_version":"None","publication_identifier":{"issn":[],"eissn":[]},"intvolume":" 24","volume":24,"uri_base":"https://research-explorer.ista.ac.at","article_type":"original","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"King","first_name":"V."},{"first_name":"T.","last_name":"Warnow"}],"creator":{"login":"amukund","id":"72615eeb-f1f3-11ec-aa25-d4573ddc34fd"},"scopus_import":"1","dini_type":"doc-type:article","page":"1-13","dc":{"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/pl00009268","info:eu-repo/semantics/altIdentifier/issn/0178-4617","info:eu-repo/semantics/altIdentifier/issn/1432-0541"],"creator":["Henzinger, Monika H","King, V.","Warnow, T."],"publisher":["Springer Nature"],"identifier":["https://research-explorer.ista.ac.at/record/11679"],"title":["Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology"],"subject":["Algorithms","Data structures","Evolutionary biology","Theory of databases"],"source":["Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. *Algorithmica*. 1999;24:1-13. doi:10.1007/pl00009268"],"date":["1999"],"description":["We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n }, we let T|L denote the minimal subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T * such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n 2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes time O(N log3 n) and uses linear space. The previous best for this problem was a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n }), where b 0 is the number of batches which do not result in a new component. For our particular application, b0≤1 . If all edges are deleted, then the best previously known deterministic algorithm requires time O(mn−−√) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology."],"language":["eng"],"type":["info:eu-repo/semantics/article","doc-type:article","text","http://purl.org/coar/resource_type/c_6501"],"rights":["info:eu-repo/semantics/closedAccess"]},"day":"01","related_material":{"record":[{"status":"public","id":"11927","relation":"earlier_version"}]},"keyword":[],"abstract":[{"lang":"eng"}],"citation":{"chicago":"Henzinger, Monika, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” *Algorithmica*. Springer Nature, 1999. https://doi.org/10.1007/pl00009268.","ista":"Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.","mla":"Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” *Algorithmica*, vol. 24, Springer Nature, 1999, pp. 1–13, doi:10.1007/pl00009268.","ieee":"M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” *Algorithmica*, vol. 24. Springer Nature, pp. 1–13, 1999.","short":"M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.","apa":"Henzinger, M., King, V., & Warnow, T. (1999). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. *Algorithmica*. Springer Nature. https://doi.org/10.1007/pl00009268"},"article_processing_charge":"No","publication":"Algorithmica","date_updated":"2024-11-04T11:41:23Z"}]