{"entities":{"Q1107326":{"pageid":1118075,"ns":120,"title":"Item:Q1107326","lastrevid":69835815,"modified":"2026-04-13T10:40:24Z","type":"item","id":"Q1107326","labels":{"en":{"language":"en","value":"An optimal time algorithm for finding a maximum weight independent set in a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064508"}},"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":"Q1107326$89DEBEE9-BAF1-40FE-A6AB-06605EE9796E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"876ab8945bcd91845436cb1b243b1dc7430332bb","datavalue":{"value":{"text":"An optimal time algorithm for finding a maximum weight independent set in a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107326$675FAD34-15E4-40F4-9B06-A2224E0B4CD9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"999cb119f508f8112d664caacd33359319ff355c","datavalue":{"value":"0652.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$4C6169E2-2ECE-4C8D-AF67-4AEC3B2171EB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"29f39b0dcd2b3964130158892cdf06c5d30b0475","datavalue":{"value":"10.1007/BF01934098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$8F3DA636-0762-4745-A1D2-C977E1239B45","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107326$C2588C41-F631-4E23-A757-000F41F88E83","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107326$06A92EFA-1D7B-474C-A4B2-A9C1D65971B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1107326$BC2C59C6-2D9E-4F03-9CF5-5DDC37D174A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70e8221b8a152dfca9c85484ed3875df1ff7c086","datavalue":{"value":"The maximum weight independent set problem for a general graph is NP- hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, \\textit{Sh. Pawagi} [ibid. 27, 170-180 (1987; Zbl 0642.68128)] has presented an O(\\(| V| \\log | V|)\\) time algorithm for solving this problem on a tree. In this paper, we propose an O(\\(| V|)\\) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107326$8A6C1C33-367E-44B8-87EC-6303ACD81E80","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$00AA5802-9221-4B40-9381-B5FFE6BEC5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$9CE9D585-4340-4529-A865-AB1342357B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$AAFB1018-67A9-4B5A-A1F7-A6D1E1362B8C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1dfec67299821fece120cab8975914f9239e9018","datavalue":{"value":"4064508","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$EB46FFC5-F101-43F5-B842-8EFFE87D750A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd8b792fb742e2147c60543a6c54c82863c55388","datavalue":{"value":"maximum weight independent set in trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107326$8A892F7D-D101-496B-9100-7DA789905E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107326$2F9FAE41-D7BD-4F60-B89A-D0F7E2B748E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea719adf37185a73309d541d6bccee5d369572d","datavalue":{"value":"time optimal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107326$FA7891A2-AB12-4EA8-985D-698C1B9CF448","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":"Q1107326$8B9411BF-B6D7-41D2-83DC-ADC028C0406A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107326$3EE32DA6-44BC-43DC-A022-4C55BBB83169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"725d5a1e83f551985a8584a70cd5a84d61b8636f","datavalue":{"value":{"entity-type":"item","numeric-id":1101239,"id":"Q1101239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107326$E412213D-DDD4-42C8-B9EF-209150A6AF1F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"873af1898411b3737332fdb1e60a45aa0f2ff919","datavalue":{"value":"https://doi.org/10.1007/bf01934098","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107326$BCC9DD4F-31C8-443D-A916-447301663982","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7cd05cda0c994180d556a4886f9f9bca752c7e70","datavalue":{"value":"W1970602728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107326$8F2B3251-31BF-4AE0-A614-A37F74599273","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58284ef1431eec681093d09ad43d4d506740844e","datavalue":{"value":{"entity-type":"item","numeric-id":3210915,"id":"Q3210915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d27e3fb9a8f81b84a6486a463d23725556fbd9cc","datavalue":{"value":{"amount":"+0.90644765","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":"Q1107326$54EDBB01-5732-484F-B245-585737593D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d242062aebd0fa4d62582984cf5fb55cae7be3c","datavalue":{"value":{"entity-type":"item","numeric-id":1101239,"id":"Q1101239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d8f6a34b9d10497d0958f09766e77e712e53bd","datavalue":{"value":{"amount":"+0.90175426","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":"Q1107326$520B4BA5-B722-4DDA-A5F1-F73CE10E61AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d7222624b6a1c73c6ec7d42a155b7d094694e72","datavalue":{"value":{"entity-type":"item","numeric-id":4511244,"id":"Q4511244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55f24561777dc436c6beaaeba1b6f4b8d86ce8bf","datavalue":{"value":{"amount":"+0.8970088","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":"Q1107326$2C038B1F-2BC2-482E-875C-05FDECCC8836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b930beb0ec9ae6bd735dbc9b14caad6c2ee1a4f","datavalue":{"value":{"entity-type":"item","numeric-id":1199945,"id":"Q1199945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"038411f0c707c8e187f75272c45f28462f1d9418","datavalue":{"value":{"amount":"+0.89238423","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":"Q1107326$2F8E926C-5DA4-46EA-BC7B-9875C113D8E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f26d9ca2d4564d6d5e87b993d791a121cddc1c50","datavalue":{"value":{"entity-type":"item","numeric-id":378171,"id":"Q378171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06893f2a02b3895ab57dd789ec3597cff830ec7b","datavalue":{"value":{"amount":"+0.8920617","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":"Q1107326$5E6687F5-A5A8-49A5-9D13-5125C029328B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6892cc283d6911a3b9daa1ab27a2af961373c746","datavalue":{"value":{"entity-type":"item","numeric-id":4368403,"id":"Q4368403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18cb942728668bf983c882cf3342e75615f41766","datavalue":{"value":{"amount":"+0.89189494","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":"Q1107326$011E229A-DEBB-4F5C-9DB1-6B1C3A4C5A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2d87a1a733ef8b9040ed3a91dd8ee2854a82feb","datavalue":{"value":{"entity-type":"item","numeric-id":680149,"id":"Q680149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"492cd545d574c9126cc88dda5fbe3d72008a8fb7","datavalue":{"value":{"amount":"+0.8877353","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":"Q1107326$642696C3-A518-4A07-A7A2-BCF09A2D0D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcf889fe6a71b9c8d56140d544c72f66d7cbb653","datavalue":{"value":{"entity-type":"item","numeric-id":1679914,"id":"Q1679914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7778d2ee98046b35f704026ea7156021bc21e682","datavalue":{"value":{"amount":"+0.88729215","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":"Q1107326$F62DFDCC-DE94-422D-9B7E-7C8ECCB959C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f490873ce6aa30a430dc970e80723747177e778","datavalue":{"value":{"entity-type":"item","numeric-id":1861582,"id":"Q1861582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56f5428831d1baa29e19f06b453be6941418ef0d","datavalue":{"value":{"amount":"+0.88184476","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":"Q1107326$7A982E9F-77F3-4676-9211-2169F6E2EC34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b246b81614648d0705267795b9a14a0880624565","datavalue":{"value":{"entity-type":"item","numeric-id":987822,"id":"Q987822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aad191bbb3e93abe0f79c102b1de3b87de2fbc09","datavalue":{"value":{"amount":"+0.88040996","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":"Q1107326$908F74CC-9BEA-4AFF-9096-5AFA7FF0AA23","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal time algorithm for finding a maximum weight independent set in a tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_time_algorithm_for_finding_a_maximum_weight_independent_set_in_a_tree"}}}}}