{"entities":{"Q1842656":{"pageid":1853398,"ns":120,"title":"Item:Q1842656","lastrevid":69096648,"modified":"2026-04-13T04:45:48Z","type":"item","id":"Q1842656","labels":{"en":{"language":"en","value":"Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 750905"}},"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":"Q1842656$37501B42-A94D-4FD3-94B0-567F62C0C70E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4609efe749456da5a678d066274f5b522d5b6d9d","datavalue":{"value":{"text":"Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1842656$9402DA0D-6B6E-4333-B6D2-2A05B3D51F40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5fd44e5a9c898436e6a1c02a8cd76443b7047d60","datavalue":{"value":"0822.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842656$FACDC645-1279-4F58-84F9-426A4631B577","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"70828667bdec74039b6482bb90a5f78b5e9e6014","datavalue":{"value":"10.1016/0166-218X(94)00089-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842656$15254247-52CD-4E44-B33F-B9BAB4EB5351","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bd99720aabea80caac5fa193fc84d7ae48f389c","datavalue":{"value":{"entity-type":"item","numeric-id":799668,"id":"Q799668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842656$E19C7567-B2D6-429D-B261-F8D326AF8F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afab4fa90e34d11a8878a06ab7e4a5229732fa5d","datavalue":{"value":{"entity-type":"item","numeric-id":1113915,"id":"Q1113915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842656$68BD02A6-FD83-4189-B227-0463D0A9BFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"76935e322252a569fb178e52d51f93a212d31833","datavalue":{"value":{"entity-type":"item","numeric-id":1842655,"id":"Q1842655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842656$F08CBFF1-7729-47FF-A3CF-D2AA4210BC4A","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":"Q1842656$C38A7FCC-CC50-448D-8A21-029BD9449482","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1bb05cfab2ff143abac941712f0af70d5b1e91aa","datavalue":{"value":{"time":"+1995-10-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1842656$05E53B0D-6ECC-434E-B7F8-E7C921D1BF2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f2e794c58dbb0fe1e54958862f02416fe7ba48ea","datavalue":{"value":"Let \\(T= (V_ 0\\cup V_ H, E, \\sigma)\\) be any tree where \\(V_ 0\\) is the set of leaves, \\(V_ H\\) is the set of internal nodes, \\(E\\) is the set of branches, and \\(\\sigma\\) is a function over \\(V_ 0\\) with real or natural values. Such a tree is called an evaluated leaf tree, or briefly an el- tree. Let \\(\\lambda\\) be an assignment for the vertices of an el-tree such that \\(\\lambda| V_ 0= \\sigma\\), called an reconstruction on \\(T\\). Set  \\[ L(\\lambda)= \\sum_{\\{u, v\\}\\in E} | \\lambda(u)- \\lambda(v)|. \\]  The paper considers the following optimization problems: (1) Determine the minimum value for \\(L(\\lambda)\\) over all reconstructions on \\(T\\). (2) Find a reconstruction which attains this value. The authors present a solution for the problems by introducing the concept of median interval. Also the computational complexity of this method is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$C256AE0D-B414-4D0F-8956-9A8596C265AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842656$68C53374-CF81-4E79-8773-4367247B5F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f8ceb942b522b8d01fe3ace5f2c6d53133530f84","datavalue":{"value":"92B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842656$6D259669-169A-4066-A8AC-130926FCAC3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842656$B14C42B7-4659-4978-B48C-32677455361D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"193237e7ceb281dad0c9efbfcb9a6f1d5c7d977a","datavalue":{"value":"750905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842656$C3233CCF-0EF7-4251-B50E-5DF36F88EAA9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8213f62b304b3f19fc8e047157f199fa021350d2","datavalue":{"value":"Farris-Swofford-Maddison method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$24454DCA-FC97-4E0B-AAAE-D25D0B31B768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$4C6AE0C6-2A20-4CDC-9AF9-6CC0E57DE655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eabdeb96accd1d948d1b5435d21853df4c64ecc7","datavalue":{"value":"evaluated leaf tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$982BCB39-3B63-43A5-9B26-EC37675476CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20cb5f900346d6218be2e7d1c87b3ca77a3b494d","datavalue":{"value":"reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$74300F5F-E07F-49E2-B23F-CB1A22DE8363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"406fee276d185643b3ea44cfa9b501b989c05826","datavalue":{"value":"median interval","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$70800F67-59A3-4772-B06F-2014C5DE5C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842656$57353699-3A1F-4A6F-B03B-FC509A7FCA92","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1b54857edcab7426c17c1bfaeb67b1f001fa1741","datavalue":{"value":{"entity-type":"item","numeric-id":587985,"id":"Q587985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842656$617DFF8E-4F23-4A9F-A636-49C04DFDC3A0","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":"Q1842656$D07C1B6F-3D51-4B5B-AE12-B917888B45D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842656$FB74FABB-EBCE-4F7E-ABA3-D66C5A8FC872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c59d144b933c3b38ec77336e98543b217584e38","datavalue":{"value":{"entity-type":"item","numeric-id":1121196,"id":"Q1121196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842656$63154B75-EF84-4CB2-BCE2-5FDAD233F85F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"250ee02f91284b7808d4d1d3657c18299658a784","datavalue":{"value":{"entity-type":"item","numeric-id":644569,"id":"Q644569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5976712aa6affb20b60a56b9afb843e8b5bbb615","datavalue":{"value":{"amount":"+0.8776375","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":"Q1842656$EEFCC4C3-DB32-4FAF-91BB-D3873C5FB863","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4972eb8688fa1545688f48613b8c25050be0179c","datavalue":{"value":{"entity-type":"item","numeric-id":2500323,"id":"Q2500323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7202b3090c0d3be917acacab8b10d15054f18055","datavalue":{"value":{"amount":"+0.86919945","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":"Q1842656$1B9BD137-2662-48CE-AD21-6A6C3C3D8A05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f24fa8da78476b488008656794fa56a9a17b93ed","datavalue":{"value":{"entity-type":"item","numeric-id":4417678,"id":"Q4417678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc6c4720a18dee4ded40538578797aa9bf4deed4","datavalue":{"value":{"amount":"+0.8689293","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":"Q1842656$32E62676-F8F8-4064-B43F-784F708A7DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3ced0e3c9086f7b4653a7784c2b83639dc6786f","datavalue":{"value":{"entity-type":"item","numeric-id":2725837,"id":"Q2725837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeb3fb37ec42ea436b078b7b078ce9a89a0140f7","datavalue":{"value":{"amount":"+0.86166465","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":"Q1842656$8BA6CFDD-8345-48F4-919D-1BB260679A76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"902756710be32e7300d4a058ef62dc39917fe962","datavalue":{"value":{"entity-type":"item","numeric-id":5192034,"id":"Q5192034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"324d821860c292fda2348c7b222a1b64279d319d","datavalue":{"value":{"amount":"+0.85760856","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":"Q1842656$15F91755-2845-4267-8452-3B7BE1754A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4502b473b32215c8dc9bcd73edcb5d4701f87418","datavalue":{"value":{"entity-type":"item","numeric-id":1636052,"id":"Q1636052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7185a991b58157f07e0ee01fbd96f0f9196ac27","datavalue":{"value":{"amount":"+0.8532294","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":"Q1842656$E307437A-D4B3-40E9-A6BE-6E141F74932C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generating_most_parsimonious_reconstructions_on_a_tree:_A_generalization_of_the_Farris-Swofford-Maddison_method"}}}}}