{"entities":{"Q1764471":{"pageid":1775213,"ns":120,"title":"Item:Q1764471","lastrevid":82123811,"modified":"2026-05-06T20:09:33Z","type":"item","id":"Q1764471","labels":{"en":{"language":"en","value":"On the computational complexity of the rooted subtree prune and regraft distance"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2138552"}},"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":"Q1764471$601F57CC-BE63-494B-9BE9-62267B60C571","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5cf33df13fa507d5879e7d3471ce0936b7dcce98","datavalue":{"value":{"text":"On the computational complexity of the rooted subtree prune and regraft distance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1764471$9E28AAA7-2CFD-43F2-86CD-DFE13C9629F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"daa7241b229278057bd98e2d406e9edfb0e6f1e0","datavalue":{"value":"1059.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$3187B430-AFD7-4DA9-939F-DF656040F099","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"27d2b3b518bae3ac372bfceb60331f357c879368","datavalue":{"value":{"entity-type":"item","numeric-id":281903,"id":"Q281903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764471$8502B8AC-6F2D-4A64-9A11-259112D59F20","rank":"normal"},{"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":"Q1764471$E86C207E-618D-4051-9564-319D067A6D58","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"710cc084d2ed0d09beceb5d2d7c52611268d6193","datavalue":{"value":{"entity-type":"item","numeric-id":159225,"id":"Q159225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764471$61E8137A-6504-404E-A90A-6FF2886FD6B0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ccd3afca070fb9c1f222b2e6f71567886f3a19c1","datavalue":{"value":{"time":"+2005-02-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1764471$F241596C-3C0B-43F7-BA8D-A3CE5B064A57","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a58c15f5329bb696c46ae14a06a78ada85d1a8e","datavalue":{"value":"http://dro.dur.ac.uk/613/1/613.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q1764471$99C2C05D-B0DD-42E6-A40E-776F12E09225","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"631e04b96d6630b331985a1578ae587c54467466","datavalue":{"value":"The paper proves that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard -- solving a longstanding problem. (This operation cuts off a subtree and reattaches it to another part of the tree.)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764471$CBCD9F32-94E0-4B1C-8A32-0D4E4BA2E02A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"01b0989d65d3fe37f1a608a8cd96e416bda56c38","datavalue":{"value":{"entity-type":"item","numeric-id":200913,"id":"Q200913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1764471$7B1AF067-EBA5-444B-807E-C1600A48EDA9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$8989F40E-978A-49D7-9DB3-E0347948A5BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"628b6504534c9c491a1aed9f9fa031e89a793c1f","datavalue":{"value":"92D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$27890503-AE56-4010-B412-6A8F052B042E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc1983c372e04fc8e3f53dc3a915ea8cd206ac00","datavalue":{"value":"2138552","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$42D566FD-1982-4AAD-AE8C-6F659EAA6528","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06b8006c86917e84b1f67710eee129b910e8de64","datavalue":{"value":"rooted phylogenetic tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764471$9EF87B3D-2DE0-45CD-B4E4-362E631C1E20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04e4376b2a2914c93814bcddb3c3ac2a19db17d9","datavalue":{"value":"rooted subtree prune and regraft","type":"string"},"datatype":"string"},"type":"statement","id":"Q1764471$AA832A03-B294-4B1F-8A9D-FAA1454049AD","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":"Q1764471$7421624C-094C-4F84-9020-D79EA2D4AA7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7137c09284e363afc5a8ccb689b374fad9f06f91","datavalue":{"value":"W1982901388","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$7A9DF09E-DDF1-4874-86BE-BF9769DDF09D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"34ee6c0cb94f57cb007da83b075e5d7c523f27c4","datavalue":{"value":"Q104141373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$F947C722-3A5D-47F9-9C5C-4391262CC7E6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7ee2ac157e11520e9b7745b1198875bc85e258a","datavalue":{"value":"10.1007/S00026-004-0229-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1764471$2508B60D-D568-4C9D-A395-9BC1F12CFE5E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6f8c555c4c571b9369f3bc308d8495e791007a4","datavalue":{"value":{"entity-type":"item","numeric-id":2680228,"id":"Q2680228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2ab3200e47fbf2a5164bc492c706c7281efd419","datavalue":{"value":{"amount":"+0.88228536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$B6C78D49-9CC5-4EDB-8230-FA549C6110C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0da72bc943c7221ec37dc307d63156d9eb21add5","datavalue":{"value":{"entity-type":"item","numeric-id":3434562,"id":"Q3434562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2206993537c02f9ac34ffbc29b8789bd3409c421","datavalue":{"value":{"amount":"+0.8809458","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$8F05740B-20A4-4F69-A4DA-B7CED7672522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27fcde9619957c7b3d053253b530144ca5dcb5bd","datavalue":{"value":{"entity-type":"item","numeric-id":2958316,"id":"Q2958316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe2615e21de3b5740fca911d232cb41fa0117ef3","datavalue":{"value":{"amount":"+0.87912965","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$58A1BA5D-5DB3-411E-B1B9-5C52D94C0CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac33e255c7ce6536ca7a8624f44a8cc0d0fb4f64","datavalue":{"value":{"entity-type":"item","numeric-id":2115868,"id":"Q2115868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcc5bf33c36b300a29c77a50812bb31052848585","datavalue":{"value":{"amount":"+0.8741095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$97AA4E4A-F049-43F5-AF65-3A6F7214DE89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ee7eb039438f9e6451f5c3d8c79f93d28de6bba","datavalue":{"value":{"entity-type":"item","numeric-id":3521928,"id":"Q3521928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dc46a5094a5ce391096e331e103d5b86dac6e25","datavalue":{"value":{"amount":"+0.86727715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$1F2ADCB5-022B-4EE1-A165-14B98BA5F8E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dddc61e5938f1d87eb36da445e2d7aeddeb30c2","datavalue":{"value":{"entity-type":"item","numeric-id":1987233,"id":"Q1987233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7f6dafc94c37e2c4c58b870dcd37878bfe08bd6","datavalue":{"value":{"amount":"+0.8660907","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$C31CEA15-1315-436C-B18A-130E9CDA47FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1730d44680aaf47cf2618f91832477adfdb4622","datavalue":{"value":{"entity-type":"item","numeric-id":2819486,"id":"Q2819486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7f6dafc94c37e2c4c58b870dcd37878bfe08bd6","datavalue":{"value":{"amount":"+0.8660907","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$2250ED61-52BD-41D1-BF24-C5FAE82CDAD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c029ecce1a35d28bc72f14b5c6b374f7c0723cc","datavalue":{"value":{"entity-type":"item","numeric-id":1935809,"id":"Q1935809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"034bcad5bfa555379779daf8932df577ea130463","datavalue":{"value":{"amount":"+0.86356044","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$151A1D49-8EB9-4CC7-B16A-BBFAA01CA5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7fe33c3281961c5c8e0c00850da7e6b85d85bbd","datavalue":{"value":{"entity-type":"item","numeric-id":2348030,"id":"Q2348030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7495356caeeb4f6c9301e54443fa15a9e42a51f8","datavalue":{"value":{"amount":"+0.8635171","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1764471$EB851D93-2200-41DF-A585-737278F5444B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of the rooted subtree prune and regraft distance","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_computational_complexity_of_the_rooted_subtree_prune_and_regraft_distance"}}}}}