{"entities":{"Q1736566":{"pageid":1747307,"ns":120,"title":"Item:Q1736566","lastrevid":72377763,"modified":"2026-04-14T04:29:57Z","type":"item","id":"Q1736566","labels":{"en":{"language":"en","value":"New heuristics for rooted triplet consistency"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042167"}},"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":"Q1736566$E0B92364-DC7D-4A23-A88A-F62CCA21C8B1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cbe51c1573db309018a56c29d813a524a2360176","datavalue":{"value":{"text":"New heuristics for rooted triplet consistency","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736566$F8F1ED7D-E576-4961-B999-253F05B10A40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4ca3b2c8dbf749d930eeb9e905934e7f38ccc7c","datavalue":{"value":"1461.92065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$FED5AC8F-61A0-4862-8B15-9E8743F52C9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"35012ba0638fac9355eff06a89a3a3f1bd11ae3b","datavalue":{"value":{"entity-type":"item","numeric-id":1736564,"id":"Q1736564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$0DA90BEF-DDE5-460F-9928-0EE9D8986EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da4b6376df740f3bb1d547f1226a7e412c76ab32","datavalue":{"value":{"entity-type":"item","numeric-id":314739,"id":"Q314739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$1C877D04-31FD-4AC2-BAE8-FDF0C50AB042","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e25d1d209b858b1db679b4e9ebc023f62cd4665","datavalue":{"value":{"entity-type":"item","numeric-id":1736565,"id":"Q1736565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$E848623F-3178-491C-B980-3CF14A823AE7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$39EE6ADB-0388-4E44-943F-6149D967A35A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736566$979B0698-262D-48DB-BEA5-227BE1C52CEF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5d5be08bb1c172f19201c45f74bc3f58a8dee03a","datavalue":{"value":"Summary: Rooted triplets are becoming one of the most important types of input for reconstructing rooted phylogenies. A rooted triplet is a phylogenetic tree on three leaves and shows the evolutionary relationship of the corresponding three species. In this paper, we investigate the problem of inferring the maximum consensus evolutionary tree from a set of rooted triplets. This problem is known to be APX-hard. We present two new heuristic algorithms. For a given set of \\(m\\) triplets on \\(n\\) species, the \\textit{FastTree} algorithm runs in \\(O(m + \\alpha(n) n^2)\\) time, where \\(\\alpha(n)\\) is the functional inverse of Ackermann's function. This is faster than any other previously known algorithms, although the outcome is less satisfactory. The Best Pair Merge with Total Reconstruction (BPMTR) algorithm runs in \\(O(m n^3)\\) time and, on average, performs better than any other previously known algorithms for this problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736566$334CC6C8-7D32-44DB-9B67-CCBD81EEEDA8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8acfb5681686a479769f1498162f25169e468cda","datavalue":{"value":"92D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$3F66EC82-B8BF-4EEE-982C-5B811D069E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$553B7C29-78F8-4B2E-A10C-71E8BBD95977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"628b6504534c9c491a1aed9f9fa031e89a793c1f","datavalue":{"value":"92D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$EB5EE60F-8CC3-4A07-832D-D2949519736D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$BB93129F-A494-46FD-84A4-EDD39A8E8A13","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9152c8cdcfe639e51821a3df19a40eaeab606220","datavalue":{"value":"7042167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$0EAE66B4-A1DF-4AA4-9A01-F0698317A854","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"920d484044cdbef5ac2e5988f2c5573fe3eed4b5","datavalue":{"value":"phylogenetic tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736566$832F2490-F739-42F2-9204-25EB378F0E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e18be82a82fe96f3a8b1d2fde1b308e0c19a6db6","datavalue":{"value":"rooted triplet","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736566$88CFB798-C689-4F2C-9A09-07B5CCE56302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d8d8518f02e16871c7c31676b9f8c704be7d8cd","datavalue":{"value":"consensus tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736566$86C16C7B-C004-46BC-A2F0-9A961FAA1FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736566$5ECBA013-2D15-4980-809E-2B50D1D873C9","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":"Q1736566$E8C1D043-9D39-4554-A82F-DFDBE0C8B296","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"66bad4c7c97cf2ecb610a9c8f447cea4b9a4e67c","datavalue":{"value":"https://doi.org/10.3390/a6030396","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736566$3AE44316-03A9-4D4F-8B54-4FEB9BB2883B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e2afe2e3bd4d06907638f9ab02d4f4bec276b879","datavalue":{"value":"W2129484641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$B4D897D3-921E-4695-9B48-5D607A279304","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aa5af4a593093e36b6a3d9275e26b692621bf07","datavalue":{"value":{"entity-type":"item","numeric-id":4801154,"id":"Q4801154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$D309E387-0340-44A5-A0B3-034CD7C49E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da6036416ace3b40803d08b4eccd3605987ddc7a","datavalue":{"value":{"entity-type":"item","numeric-id":4895795,"id":"Q4895795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$E980372A-5F43-4270-BD1A-1132648035BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6268eb48fab00d338fcebf93799e79848352b797","datavalue":{"value":{"entity-type":"item","numeric-id":2266938,"id":"Q2266938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$90EE71B1-3D06-4FE9-84BB-9305483FAEB6","rank":"normal"},{"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":"Q1736566$84036FB0-479A-49D4-9C46-0B04FCDA9ABD","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":"Q1736566$795AA43F-8B07-48FB-9A02-EF0D9809B06E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763cd19cb1c2ad37db61060b470f52f1b3537516","datavalue":{"value":{"entity-type":"item","numeric-id":818677,"id":"Q818677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$51A820C6-8FFB-45B4-9125-897D9134DF4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ba1ea5471ab0cb7b3379d0ad0d1e3da7dcecef","datavalue":{"value":{"entity-type":"item","numeric-id":5441357,"id":"Q5441357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$4A85C30D-FE41-4DB5-BB13-F26BAEB37A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7de16d6d82782716dd144132f7ac44cfcb5e411","datavalue":{"value":{"entity-type":"item","numeric-id":1768596,"id":"Q1768596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$55D4C523-F752-41BA-9DF6-49DB8091FE26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"515c104cc70d6b37a163d6826aed9b89d6d0a7bf","datavalue":{"value":{"entity-type":"item","numeric-id":3596743,"id":"Q3596743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$A56EC454-A948-4C0F-B2DF-E6000D48D008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3266be2c92c61c712720de7cc54e9fd8f74a079d","datavalue":{"value":{"entity-type":"item","numeric-id":1306398,"id":"Q1306398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$EEE30048-BE50-4B8F-A30F-C983EBDF44A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755af5d9ed85511c8883f0c7d9c1144b53d6c72f","datavalue":{"value":{"entity-type":"item","numeric-id":860812,"id":"Q860812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$67B24D94-5C2D-4578-A853-4A8A90594F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$1B532C5A-DD96-416A-A411-A93D021C1006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972a8bf34e7833efe7d50db13efe7b7a685cc396","datavalue":{"value":{"entity-type":"item","numeric-id":4508365,"id":"Q4508365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$60BA19AC-C568-4CDE-8282-0EE0109CD1F3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d57639f094d10310891bf0bbe36e61275f3b4f33","datavalue":{"value":"10.3390/A6030396","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736566$7B4855CC-3F1F-49FA-892A-5DA7AC04D9E8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"379fda5c90ac645e03226d6a2e44af0d7b85719a","datavalue":{"value":{"entity-type":"item","numeric-id":1768596,"id":"Q1768596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d7f18c91f2b4adecf8b801ba79b4b335de63633","datavalue":{"value":{"amount":"+0.8689999580383301","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736566$2D19D134-6F66-42ED-BA2E-10D0F8CDB5B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21a501ef957a808d6f81d30ab304effde3fb3212","datavalue":{"value":{"entity-type":"item","numeric-id":3177802,"id":"Q3177802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27eaaa0ac65abbfeabe9e579c992c0e6e67cc9d5","datavalue":{"value":{"amount":"+0.8654190301895142","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736566$6706FF0C-875B-4AEC-9F84-EF5FA9AA8DAA","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":"7a9b336653fcf38bc6288d39cafb46892bc9e0b0","datavalue":{"value":{"amount":"+0.8647377490997314","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736566$D7711B0A-C819-4942-86B6-F5CB1B44C4F5","rank":"normal"},{"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":"622c8ae3cfb8bd5250be066e7b889f39f257e2cb","datavalue":{"value":{"amount":"+0.8616230487823486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736566$34E67796-0BB6-4BF3-8E11-DFE4E4F09C47","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":"4788b14a55cbd4c5e22648fc4180ce361f4ab299","datavalue":{"value":{"amount":"+0.8404703736305237","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736566$823834E5-8953-4F60-BC55-ECC70B9A6828","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736566$1FF8E877-DB1F-4145-827E-AFCE9419B20B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New heuristics for rooted triplet consistency","badges":[]}}}}}