{"entities":{"Q405205":{"pageid":406972,"ns":120,"title":"Item:Q405205","lastrevid":61642554,"modified":"2026-04-11T00:40:04Z","type":"item","id":"Q405205","labels":{"en":{"language":"en","value":"Tree reconstruction from triplet cover distances"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340182"}},"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":"Q405205$E49FBC62-C965-4206-B4EE-7655C45F1ED0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9984ae36204e4b8837263435dcd69904ee13ca50","datavalue":{"value":{"text":"Tree reconstruction from triplet cover distances","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405205$1FB209A5-A49A-463C-A55C-61CFBF49D9AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d48fa5d384f56ba26ef616013b102c65a3af80bc","datavalue":{"value":"1300.05182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$A9E988D1-F412-4FB7-81C7-BCAA8208AFC8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"925fa53e24ad2c712da0c663b51f980652c4c244","datavalue":{"value":{"entity-type":"item","numeric-id":307585,"id":"Q307585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$1D0623D9-4517-48C1-9F76-639672BB0868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"75f44fd5176cfaeb1c41f3609e0533bcbc86cf5d","datavalue":{"value":{"entity-type":"item","numeric-id":659797,"id":"Q659797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$1DDC005A-3B23-4BD0-9A19-F8AA7B9544E3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$7BE245B5-2721-45B5-BBBA-931599405BE0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405205$C209EF68-2CA7-4571-8DC7-8217FAB05B17","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80554178e673fbc2ce92231b1c1b5c921c558cd7","datavalue":{"value":"https://arxiv.org/abs/1209.2391","type":"string"},"datatype":"url"},"type":"statement","id":"Q405205$A79119F6-DA61-424C-AB42-4A9C8B930A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"b618f737addab913df499b1b8dbfb424766313c8","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p15","type":"string"},"datatype":"url"},"type":"statement","id":"Q405205$C86EEA23-80B7-40D6-892C-2AEFDD5CC94D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d3f684f19c81e465ecc935528d30ef64d91e465d","datavalue":{"value":"Summary: It is a classical result that any finite tree with positively weighted edges, and without vertices of degree 2, is uniquely determined by the weighted path distance between each pair of leaves. Moreover, it is possible for a (small) strict subset \\(\\mathcal{L}\\) of leaf pairs to suffice for reconstructing the tree and its edge weights, given just the distances between the leaf pairs in \\(\\mathcal{L}\\). It is known that any set \\({\\mathcal L}\\) with this property for a tree in which all interior vertices have degree 3 must form a cover for \\(T\\) -- that is, for each interior vertex \\(v\\) of \\(T\\), \\({\\mathcal L}\\) must contain a pair of leaves from each pair of the three components of \\(T-v\\). Here we provide a partial converse of this result by showing that if a set \\({\\mathcal L}\\) of leaf pairs forms a cover of a certain type for such a tree \\(T\\) then \\(T\\) and its edge weights can be uniquely determined from the distances between the pairs of leaves in \\({\\mathcal L}\\). Moreover, there is a polynomial-time algorithm for achieving this reconstruction. The result establishes a special case of a recent question concerning `triplet covers', and is relevant to a problem arising in evolutionary genomics.","type":"string"},"datatype":"string"},"type":"statement","id":"Q405205$D3FA4D28-E803-4A42-B4D5-811A44CF613F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$EF676EBF-A2B7-4ADC-B7B6-718BA75C543A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$42AADAED-22DA-4A95-AF14-6A23AD8F60DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b2773d305bb22ed635d748bc939993c6750608ab","datavalue":{"value":"05C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$ADFEB0BD-78F2-4996-9424-3F66D36BA3A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"628b6504534c9c491a1aed9f9fa031e89a793c1f","datavalue":{"value":"92D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$7437FDA4-828A-49F5-A6F1-23EC759B9AC3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e8faf4bb434b8ea4affe01ba38dfcc8a7eb6c06","datavalue":{"value":"6340182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$4A05C1F4-D005-4D7D-B4B1-B802F7BBB9C1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2f6fc003a68b5549a7f46839dbd7ef9fac5f62c","datavalue":{"value":"X-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q405205$210118B5-F7B4-4460-866D-D5C1320E3E8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eda4059d709c231008d0cd4f4dc9dfa86bd3055f","datavalue":{"value":"tree metric","type":"string"},"datatype":"string"},"type":"statement","id":"Q405205$09B119DC-58EE-44FF-AE02-2E8FCAEEC5B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"320e8485096fd6bca253de39354f3a4034a8875b","datavalue":{"value":"tree reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q405205$32AE84DC-44B4-4E5C-A7BB-6AD0EEB4BBEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd2b47bef4e2ac9f491e85a467fb9a860d6f9c98","datavalue":{"value":"shellability","type":"string"},"datatype":"string"},"type":"statement","id":"Q405205$D08DD588-0081-480C-87B2-A51024262990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83514a1473c2e2c7771149294ec670d48290fbf3","datavalue":{"value":"triplet cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q405205$FCBDEA51-A919-4C64-B885-012B333F069A","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":"Q405205$F4ABB8B4-D8C1-43AA-9FDB-A5562277449C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"519378e1101d810c849fef96c483d737cd0c6141","datavalue":{"value":{"entity-type":"item","numeric-id":4004055,"id":"Q4004055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$EA332B88-E46E-437C-A401-C1DAD879B080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a782847348f0cff083a353cfb325bf5fba19e6a9","datavalue":{"value":{"entity-type":"item","numeric-id":1306736,"id":"Q1306736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$CD736ED7-F9AE-42E6-A983-8C55D8FEEE08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73863c642534bbcb8223172a588659ae286b5e6c","datavalue":{"value":{"entity-type":"item","numeric-id":4750658,"id":"Q4750658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$29D0AEA9-9473-4A0D-A020-9F6A18A668B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acf04309ddd0bb8389519342173caea520a572cc","datavalue":{"value":{"entity-type":"item","numeric-id":455729,"id":"Q455729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$51AF4E9A-868F-4CEB-85B0-80E8BA9E02C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe37a0f894b1bf7483958c501c7f7bc596a095ad","datavalue":{"value":{"entity-type":"item","numeric-id":1902471,"id":"Q1902471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$821F09E3-C1ED-4B44-939A-F51CC1C0555C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af69129590f8fa2b3fc897dabd7f18d79336f286","datavalue":{"value":{"entity-type":"item","numeric-id":1422428,"id":"Q1422428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$1C49DF97-943D-4DE2-82DF-AD0522BDFB6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf6af6a5d78e8a317441a566a87ee50dd940de71","datavalue":{"value":{"entity-type":"item","numeric-id":1907943,"id":"Q1907943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$45BEE917-70C4-4B3E-A9FD-CC05AF822694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4a21ff9f84d5ce737d3830c3241f7c10b6b0e6f","datavalue":{"value":{"entity-type":"item","numeric-id":4792088,"id":"Q4792088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$C3D27914-09D6-4CCB-B503-48A8B1AFE398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb5ab655ab895540908fc213c12f7a041e69695e","datavalue":{"value":{"entity-type":"item","numeric-id":4733874,"id":"Q4733874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$937A9052-ACF6-49C5-B59F-B847982CFF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec8d9586a1292cfebb28646a9729a3805e62840c","datavalue":{"value":{"entity-type":"item","numeric-id":3338288,"id":"Q3338288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405205$B3D6B17E-B553-4DFF-A24B-79322340028D","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"13a5c6e1e49bf979c4508c3e80baf65a485e4c80","datavalue":{"value":"bafkreibmuvel2ix434cbm5miw4c6ibzz3jzuunijgzyinpmzi3kzh7jrvi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405205$B34361AA-E571-4426-A4F8-DC4826FF28D6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0e8f2d5d5fd39deffa469cf7e05952618cbbce5","datavalue":{"value":{"entity-type":"item","numeric-id":1637594,"id":"Q1637594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2ab1b761ec8b40128becd06aaeb0e518104e85f","datavalue":{"value":{"amount":"+0.8784144520759583","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":"Q405205$3FA58C3F-2330-468A-B43D-606C9A7148CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71f95a074f138876eea26e613dddfee590638c95","datavalue":{"value":{"entity-type":"item","numeric-id":1679026,"id":"Q1679026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c9fddd30766d9514f79f3b2d5f152a4115c73bf","datavalue":{"value":{"amount":"+0.8648862242698669","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":"Q405205$A4B4A4B4-3543-4B7A-8AD6-89E643EBF490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23389674dd001e3645fddd71fe15bf68832f4d6d","datavalue":{"value":{"entity-type":"item","numeric-id":455729,"id":"Q455729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d845784ceb724b3afa1d1676ed727468d638244","datavalue":{"value":{"amount":"+0.8441560864448547","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":"Q405205$DA52BBB5-B1DC-4E4C-96C0-1C97F51F6EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df09b7ed5274b7e635ffd1842faaa039d9bd32a8","datavalue":{"value":{"entity-type":"item","numeric-id":659656,"id":"Q659656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"037b2c1734aac004a0965cdb56157ac76e6c153e","datavalue":{"value":{"amount":"+0.8174183368682861","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":"Q405205$5F01ED60-A38E-4C9C-9FE0-343517FD27A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"866871b75025653513325f775407fd772c207e97","datavalue":{"value":{"entity-type":"item","numeric-id":3338288,"id":"Q3338288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"facdd67f9545b93119635f4fe4dbd2e111879891","datavalue":{"value":{"amount":"+0.8130676746368408","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":"Q405205$8ADCCDEF-9A77-4AFC-886A-626F6CA9FDF4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tree reconstruction from triplet cover distances","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tree_reconstruction_from_triplet_cover_distances"}}}}}