{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,14]],"date-time":"2026-09-14T18:23:56Z","timestamp":1789410236735,"version":"build-2803163510"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>The inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields such as biology and historical linguistics, and many models for inferring this consensus have been proposed. In this paper we present a model for deriving what we call a local consensus treeT from a set of trees ${\\cal T}$. The model we propose presumes a function f, called a total local consensus function, which determines for every triple A of species, the form that the local consensus tree should take on A. We show that all local consensus trees, when they exist, can be constructed in polynomial time and that many fundamental problems can be solved in linear time. We also consider partial local consensus functions and study optimization problems under this model. We present linear time algorithms for several variations. Finally we point out that the local consensus approach ties together many previous approaches to constructing consensus trees.<\/jats:p>","DOI":"10.1137\/s0097539795287642","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1695-1724","source":"Crossref","is-referenced-by-count":16,"title":["Computing the Local Consensus of Trees"],"prefix":"10.1137","volume":"27","author":[{"given":"Sampath","family":"Kannan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tandy","family":"Warnow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shibu","family":"Yooseph","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894192"},{"key":"R2","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0404028"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894194"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01734101"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1995.1020"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1111\/j.2044-8317.1981.tb00626.x"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908061"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(75)90040-1"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90141-2"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(76)90035-3"},{"key":"R13","unstructured":"M. Farach and M. Thorup,\n                      Optimal evolutionary tree comparison by sparse dynamic programming\n                      , in Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, November 1994, pp. 770\u2013779."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00110-X"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1086\/412935"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908078"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230210104"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0035"},{"key":"R19","unstructured":"D. Keselman and A. Amir,\n                      Maximum agreement subtree in a set of evolutionary trees\u2014Metrics and efficient algorithms\n                      , in Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, November 1996, pp. 758\u2013769."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R21","unstructured":"Monika Henzinger, Valerie King, Tandy Warnow, Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology, ACM, New York, 1996, 333\u201334096k:92008"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.2307\/2412995"},{"key":"R23","unstructured":"F. McMorris and M. Steel,\n                      The complexity of the median procedure for binary trees\n                      , in Proc. 4th Conference of the International Federation of Classification Societies, Paris, 1993;"},{"key":"R23","unstructured":"Stud. Classification Data Anal. Knowledge Organ., by Springer\u2010Verlag, to appear."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90181-8"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1018"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795287642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:18Z","timestamp":1787336058000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795287642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795287642"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795287642","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}