{"entities":{"Q1811070":{"pageid":1821812,"ns":120,"title":"Item:Q1811070","lastrevid":69018375,"modified":"2026-04-13T03:46:11Z","type":"item","id":"Q1811070","labels":{"en":{"language":"en","value":"Reconstructing minimal rooted trees."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1925253"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$F0286332-6719-4810-B444-FCB6666AA22E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff1c838a7a0445ba5de8224415e2649661e2c0f8","datavalue":{"value":{"text":"Reconstructing minimal rooted trees.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1811070$3266D3B8-653A-4FFF-B88A-E12E3ED7A8ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9cf01767b92e5af8a2e7e408047d1ff996595761","datavalue":{"value":"1038.05014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811070$2075ED27-DA5E-4BFA-8151-5D88682F94E7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"366d9a71ce36b003c417f01836eb3221362307cf","datavalue":{"value":"10.1016/S0166-218X(02)00250-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811070$8828806B-210A-470C-9751-F59B23C6E95B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"08d76fdbd7a1376ea2d6519ca78a5fe6270d7a55","datavalue":{"value":{"entity-type":"item","numeric-id":234401,"id":"Q234401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$1D85B907-A09F-4DFC-96BE-B3B5EB1B7317","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$A81FDCD7-6519-46B1-A3B8-0F513FC6EDC2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae38298a411e50615364cd6c80d7e0f949b3a896","datavalue":{"value":{"time":"+2003-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1811070$9D85A426-DBCE-4461-8B54-4945ED2471A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b8a8b66fcc546dd7dd609648a23eccca43306c63","datavalue":{"value":"A fundamental task in evolutionary biology is to combine a collection of rooted phylogenetic trees (input trees) into a single rooted phylogenetic tree (the output tree), whose leaf set consists of the union of the leaf sets of the input trees and which also displays all of the input trees. This is sometimes known as the supertree problem, and it may not be possible to solve it if the input trees carry conflicting information. In this paper only the case where the input trees carry no conflicting information is considered, that is, the case where the trees are consistent. In \\textit{A. V. Aho} et al. [SIAM J. Comput. 10, 405--421 (1981; Zbl 0462.68086)] an algorithm is presented that determines in polynomial time if a collection of rooted triples (rooted trees with three leaves) is consistent or not, and, if it is, outputs a tree consistent with the triples. Moreover, in \\textit{M. Constantinescu} and \\textit{D. Sankoff} [J. Classif. 12, No. 1, 101--112 (1995; Zbl 0829.92013)] and \\textit{M. P. Ng} and \\textit{N. C. Wormald} [Discrete Appl. Math. 69, No. 1--2, 19--31 (1996; Zbl 0868.05019)] algorithms are presented that can output all trees displaying a consistent collection of rooted triples. Building upon these studies, this paper presents two main results. First, an algorithm is presented that finds the set of all minimal rooted phylogenetic trees displaying a consistent collection of rooted triples. This constructs each such tree in polynomial time (although it is shown that there be exponentially many such trees). Second, for a collection of consistent rooted triples, a characterization is given of the tree output by the Aho et al. algorithm with respect to the set of minimal trees displaying the triples, that is based on the clusters in this tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811070$2C1EE9AE-5BC7-498F-9C78-4980AD054FAE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811070$2DDE4B96-3D69-4773-89A1-5954DAA8A4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"628b6504534c9c491a1aed9f9fa031e89a793c1f","datavalue":{"value":"92D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811070$3411A801-2E8C-48F4-BD7A-FF4A8A88214D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d6a9fd8c45ff65a189141122051855ee594899b","datavalue":{"value":"1925253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811070$741CB443-8E6D-4170-8C55-32464D3EF61D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"920d484044cdbef5ac2e5988f2c5573fe3eed4b5","datavalue":{"value":"phylogenetic tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811070$72894C13-64D3-4DE1-BE38-6C2B3FB44371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5aaaf1bd5e43c9695758ed1266593afcf2091ed3","datavalue":{"value":"rooted triples","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811070$F574DC5C-4FF0-48C3-8D08-B43C37B5E08D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec925930cd5cb92d73c0f9b0b994159f9e248e79","datavalue":{"value":"clusters","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811070$444A0E57-0DC3-4C0F-8434-E04F4CE5548E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dffee659e2514f9d0a6c28f658b5d8fd88b3df6","datavalue":{"value":"tree compatibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811070$64453551-040A-4FA3-BD7E-E1CDEA3097B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b02ff9c6ac3af6e8438d37595ced44bbeceecfc7","datavalue":{"value":"supertrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811070$3435787D-B73E-4627-B395-9AA0DA386FA5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e93f9be79f667a647be54879872e6a214a1ecc7e","datavalue":{"value":{"entity-type":"item","numeric-id":1295607,"id":"Q1295607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$4D387B35-20F3-4F92-9056-454D687096B6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$6F7D6EC9-9E73-4192-8A4E-2C9763223CAF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49bda588443f01d9e783c0ce0409d89eac168eed","datavalue":{"value":{"entity-type":"item","numeric-id":3912082,"id":"Q3912082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$16DC6475-6042-48C1-A7D5-9006ADC07E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79d0777dcf64a2a770ac2e8dea77950e2f0463c4","datavalue":{"value":{"entity-type":"item","numeric-id":1914784,"id":"Q1914784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$8CA45CEC-94F7-49F5-9BF2-3669A5E489C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32084a289eff2c6368eeb08b778a68232f5aef54","datavalue":{"value":{"entity-type":"item","numeric-id":1901397,"id":"Q1901397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$76B8F702-4A20-40F3-802B-F956F1F07A2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96cb73f46911a8b4608f55d26bdf1d8f602e600b","datavalue":{"value":{"entity-type":"item","numeric-id":1293865,"id":"Q1293865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$6C61062C-BBFE-4B08-BFEA-546312208E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d44de9b113899a47cf284e416a0aff44a0c3c7","datavalue":{"value":{"entity-type":"item","numeric-id":1923599,"id":"Q1923599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$C67A5436-18D1-458A-A111-1C51CB97DE78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6320a79ca47932370f64ccd8d371ab50cc5c65c","datavalue":{"value":{"entity-type":"item","numeric-id":1203103,"id":"Q1203103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811070$15AB5314-37FD-470C-B98C-E3BC0ADF5B67","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"98f0483010ec4ba0ecbe72cd712dbfffa3267dc9","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(02)00250-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1811070$526D1208-13DA-4872-B9F3-2DD2C46693D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7781bf98acea23be5bb3ecad64d56270533293a7","datavalue":{"value":"W2043950637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811070$6C359CDE-52BA-4516-BA70-D039E6687FCE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"715d8f116e5edabace797cbe8f73c2d1335e9449","datavalue":{"value":{"entity-type":"item","numeric-id":708349,"id":"Q708349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9914a7267d6684029a6f207e3213ab4906535a32","datavalue":{"value":{"amount":"+0.8853968","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$57B32642-FC5E-4064-B103-10F9794EF0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42b8057d15654a33a43314187af01136e9738541","datavalue":{"value":{"entity-type":"item","numeric-id":3596743,"id":"Q3596743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b6c9baaf6c0b2c53e1a366a7fe5253b66ef8d8b","datavalue":{"value":{"amount":"+0.8820106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$A2956B5A-791C-4A6B-8846-87B377B5F125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8572bfd304a8a173efdec74cbb2aa540fb6e0c9","datavalue":{"value":{"entity-type":"item","numeric-id":4808660,"id":"Q4808660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"311b3238cc227d7db3a0eb4d6266bfddddf74c43","datavalue":{"value":{"amount":"+0.8690441","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$E93D71DC-5C2D-408B-87C6-494BCC91E53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea123f91ea8acfe18c639e1343f82db8ad03372e","datavalue":{"value":{"entity-type":"item","numeric-id":6077843,"id":"Q6077843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7bd7cf9f012ba16e4b4d836b229469af8875d97","datavalue":{"value":{"amount":"+0.86856645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$3080704F-0DAD-48A7-BD0D-B2FFE67E02BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"342951c661c380c67691a03ac76e5aea6b08cf9c","datavalue":{"value":{"entity-type":"item","numeric-id":2884583,"id":"Q2884583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21e6bc33d0bf3becd0d52f39bb7ec470e258d237","datavalue":{"value":{"amount":"+0.8667099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$F66B5973-E11D-444B-B33D-E9D78752BBD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d31abff9cb9c6291fa2c62f47006b917a0124853","datavalue":{"value":{"entity-type":"item","numeric-id":4608616,"id":"Q4608616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8bc07a43851587a94ebeb11f8d56e59fec656d2","datavalue":{"value":{"amount":"+0.8598951","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$53AA3BF2-5B02-4D3B-A1BC-B8275DB00138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97593506a6d9691712148b30176e04420fbb26b8","datavalue":{"value":{"entity-type":"item","numeric-id":5091725,"id":"Q5091725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dea7a80c909b2a0429c5ac2a835a109a1a64cd58","datavalue":{"value":{"amount":"+0.8577581","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$E17E52CF-0C81-44D9-840F-289CB22839EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0bf4e17701a5e3c985ec7f5864167d2e1ddc2da","datavalue":{"value":{"entity-type":"item","numeric-id":1736566,"id":"Q1736566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"636d4a097c62eb9090259b4879b8471ed5c5dcb2","datavalue":{"value":{"amount":"+0.8527957","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1811070$AB0979AC-588E-4E64-94F5-EC4138880ED3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reconstructing minimal rooted trees.","badges":[]}}}}}