{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T13:16:44Z","timestamp":1774876604904,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1999,7]]},"DOI":"10.1023\/a:1009885610075","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"199-211","source":"Crossref","is-referenced-by-count":24,"title":["Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices"],"prefix":"10.1007","volume":"3","author":[{"given":"Bang Ye","family":"Wu","sequence":"first","affiliation":[]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[]},{"given":"Chuan Yi","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"211428_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0403001","volume":"3","author":"H.J. Bandelt","year":"1990","unstructured":"H.J. Bandelt, \u201cRecognition of tree metrics,\u201d SIAM Journal on Discrete Mathematics, vol. 3, no. 1, pp. 1-6, 1990.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"211428_CR2","unstructured":"N. Christofides, \u201cWorst-case analysis of a new heuristic for the travelling salesman problem,\u201d Technique Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976."},{"issue":"4","key":"211428_CR3","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1137\/0406041","volume":"6","author":"E. Dahlhaus","year":"1993","unstructured":"E. Dahlhaus, \u201cFast parallel recognition of ultrametrics and tree metrics,\u201d SIAM Journal on Discrete Mathematics, vol. 6, no. 4, pp. 523-532, 1993.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"211428_CR4","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0022-5193(83)90296-5","volume":"103","author":"W.H.E. Day","year":"1983","unstructured":"W.H.E. Day, \u201cComputationally difficult parsimony problems in phylogenetic systematics,\u201d Journal of Theoretic Biology, vol. 103, pp. 429-438, 1983.","journal-title":"Journal of Theoretic Biology"},{"issue":"4","key":"211428_CR5","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/S0092-8240(87)80007-1","volume":"49","author":"W.H.E. Day","year":"1987","unstructured":"W.H.E. Day, \u201cComputational complexity of inferring phylogenies from dissimilarity matrices,\u201d Bulletin of Mathematical Biology, vol. 49, no. 4, pp. 461-467, 1987.","journal-title":"Bulletin of Mathematical Biology"},{"key":"211428_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0025-5564(86)90161-6","volume":"81","author":"W.H.E. Day","year":"1986","unstructured":"W.H.E. Day, D.S. Johnson, and D. Sankoff, \u201cThe computational complexity of inferring rooted phylogenies by parsimony,\u201d Mathematical Biosciences, vol. 81, pp. 33-42, 1986.","journal-title":"Mathematical Biosciences"},{"key":"211428_CR7","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF01188585","volume":"13","author":"M. Farach","year":"1995","unstructured":"M. Farach, S. Kannan, and T. Warnow, \u201cA robust model for finding optimal evolutionary trees,\u201d Algorithmica, vol. 13, pp. 155-179, 1995.","journal-title":"Algorithmica"},{"key":"211428_CR8","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/BF01733209","volume":"18","author":"W.M. Fitch","year":"1981","unstructured":"W.M. Fitch, \u201cAnon-sequential method for constructing trees and hierarchical classifications,\u201d Journal of Molecular Evolution, vol. 18, pp. 30-37, 1981.","journal-title":"Journal of Molecular Evolution"},{"key":"211428_CR9","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/S0022-5193(84)80103-4","volume":"107","author":"L.R. Foulds","year":"1984","unstructured":"L.R. Foulds, \u201cMaximum savings in the Steiner problem in phylogeny,\u201d Journal of Theoretic Biology, vol. 107, pp. 471-474, 1984.","journal-title":"Journal of Theoretic Biology"},{"key":"211428_CR10","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L.R. Foulds","year":"1982","unstructured":"L.R. Foulds and R.L. Graham, \u201cThe Steiner problem in phylogeny is NP-complete,\u201d Advances in Applied Mathematics, vol. 3, pp. 43-49, 1982.","journal-title":"Advances in Applied Mathematics"},{"key":"211428_CR11","volume-title":"Computers and Intractability: AGuide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: AGuide to the Theory of NP-Completeness, Freeman: San Fransisco, 1979."},{"key":"211428_CR12","doi-asserted-by":"crossref","unstructured":"D. Gusfield, Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology, Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"211428_CR13","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0025-5564(82)90027-X","volume":"59","author":"M.D. Hendy","year":"1982","unstructured":"M.D. Hendy and D. Penny, \u201cBranch and bound algorithms to determine minimal evolutionary trees,\u201d Mathematical Biosciences, vol. 59, pp. 277-290, 1982.","journal-title":"Mathematical Biosciences"},{"key":"211428_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (Eds.), Plenum Press: New York, 1972, pp. 85-103."},{"issue":"5","key":"211428_CR15","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0020-0190(88)90090-7","volume":"27","author":"M. Krivanek","year":"1988","unstructured":"M. Krivanek, \u201cThe complexity of ultrametric partitions on graphs,\u201d Information Processing Letter, vol. 27, no. 5, pp. 265-270, 1988.","journal-title":"Information Processing Letter"},{"key":"211428_CR16","unstructured":"W.H. Li and D. Graur, Fundamentals of Molecular Evolution, Sinauer Associates, 1991."},{"key":"211428_CR17","volume-title":"Introduction to Combinatorial Mathematics","author":"C.L. Liu","year":"1968","unstructured":"C.L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill: New York, 1968."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009885610075.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009885610075\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009885610075.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:08:29Z","timestamp":1751281709000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009885610075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,7]]},"references-count":17,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1999,7]]}},"alternative-id":["211428"],"URL":"https:\/\/doi.org\/10.1023\/a:1009885610075","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,7]]}}}