{"entities":{"Q1101239":{"pageid":1111991,"ns":120,"title":"Item:Q1101239","lastrevid":42876689,"modified":"2025-07-15T15:30:48Z","type":"item","id":"Q1101239","labels":{"en":{"language":"en","value":"Maximum weight independent set in trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4047156"}},"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":"Q1101239$3780A267-0F32-47DB-8151-A3E02EC94613","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8fb63dcb5fbb9bb011ffb1ed3cf9883e7036ed60","datavalue":{"value":{"text":"Maximum weight independent set in trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1101239$1949511E-32E6-4EFC-B9AD-DA27A43C14A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c499224a852ac1e2508c3a3f6b697dea81a44203","datavalue":{"value":"0642.68128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101239$BC5A531F-4115-45E9-829C-7CE283EC55C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dc913a3e3403c3bd0485c845bdbabeb8c0cb8c60","datavalue":{"value":"10.1007/BF01934182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101239$9A237209-20FD-4BD6-9A9E-3FEF07D21124","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":"Q1101239$3DB19505-0FC2-4DDA-AE48-FBD6399F3A9E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1101239$81814079-44DB-4428-BB00-7E67C6429566","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b95f2ae53e820924473f8c8ac49d4ddd495a39d1","datavalue":{"value":"Computing a maximum independent set, weighted or unweighted, is NP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum wehe extent to which, given two categories A and B and a functor K from A to B, the functor K can be used to gain information on the objects of B via approximations by K-images of objects in A. In the shape geometric theory of Borsuk the category A is the homotopy category of polyhedra, B the homotopy category of compact metric spaces and K is the inclusion.    In this note the authors set out to interpret the simpler parts of categorical shape theory in terms of the basic theoretical problems of pattern recognition, namely the classification and recognition problems. In this interpretation A is a category of archetypes or models whilst B is a category of objects of interest, K being a ``comparison functor''. The consequences of such a basic recognition system are explored and certain problems that naturally occur in this theory are discussed with reference to pattern recognition.    The authors intend to write further notes of this form in the expectation that the ideas, suitably modified, may prove to be of use within the theory of pattern recognition.    The authors would like to point out that reference 2 is to be published under the title ``Shape theory: Categorical approximation methods'' by Ellis Horwood Ltd. (expected publication date Spring 1989).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101239$162D7B66-3954-4CAE-9D1C-6BAF5CD65303","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101239$C233BDAA-A142-4267-A252-DAD1DB846834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101239$BE1C2F00-4E80-42BD-AC80-D7C56EF7EAA5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ffddc281ce08f4c64b224562c68ceea6bb0a3977","datavalue":{"value":"4047156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101239$64B35510-C388-4287-87BF-E8CD2ED39BEA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"670027ef6deac5daa82654798de724502deb8bc9","datavalue":{"value":"maximum wehe extent to which, given two categories A and B and a functor K from A to B, the functor K can be used to gain information on the objects of B via approximations by K-images of objects in A. In the shape geometric theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101239$9F1B2C60-A520-4C70-BFC6-99BF91389E7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fde81ea46833fe18d0809d0fb95fc4b11a450f1b","datavalue":{"value":"categorical shape theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101239$C937C1DB-EC7B-466A-A2B2-22719C8470F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b508eb9c171301d8939bcc797b0cd89d2ccbd533","datavalue":{"value":"pattern recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101239$2905A06E-DCB9-42F6-890F-5ED1BD442A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f12eb165bd6cb53df1cbde83765cb1c65a6033d","datavalue":{"value":"classification","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101239$7D158C63-982C-4758-8183-D20E6A5C5DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c844f777aade7d66d5507a8365e3bfa7fcedf6f","datavalue":{"value":"comparison functor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101239$84E61CDF-639A-41E4-8C40-F11C52060E02","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbc5e6deae886df457144401fa832a4f68f01b60","datavalue":{"value":{"entity-type":"item","numeric-id":1108034,"id":"Q1108034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$0DC8A717-06CA-4D8E-A173-BAEA3003364A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ab79fdaddc189a7483164e877e59b9ea4b806d0e","datavalue":{"value":{"entity-type":"item","numeric-id":590766,"id":"Q590766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$5CE4593F-4DC1-4EBB-8ED2-170E59F22D50","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":"Q1101239$A14F48D2-0660-4E5A-948B-F6AA6B669576","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"021cb621faf897718c684e1f2aadedf19587d13a","datavalue":{"value":{"entity-type":"item","numeric-id":1062757,"id":"Q1062757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$774493E4-D69F-4271-8154-4BEC9181E3AD","rank":"normal"},{"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":"Q1101239$9A4E362A-F34C-414E-9678-A80B588CCD5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfd4a09c41cee8b655759ab17692faebdb0b063c","datavalue":{"value":{"entity-type":"item","numeric-id":1056763,"id":"Q1056763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$C16946FF-46DB-48A6-A7DC-A1C6C8477A42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ed9af1f866ef0f1aa193a9ab8e4ca4bbc605405","datavalue":{"value":{"entity-type":"item","numeric-id":3870690,"id":"Q3870690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$A3F97D14-173D-421F-BD47-2A14E4F879A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a0983ce7a664c54ed4274f83ecbe33679a4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4074668,"id":"Q4074668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$E7618925-8371-4763-B7B3-FE2675D015C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ee26c3f02a87692952463d3238e136349cd3c6","datavalue":{"value":{"entity-type":"item","numeric-id":3967060,"id":"Q3967060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$ECABDA3F-3CEA-4927-8211-B48E1C242397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0669e594826b5b3523dfa03abf605c0d6353cb8a","datavalue":{"value":{"entity-type":"item","numeric-id":1171390,"id":"Q1171390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101239$88B1EF75-8CEB-4BD6-8621-CD184CDBF969","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f3b6e6ce41c0cff08e2efedb6fc0f9fdd2a184d","datavalue":{"value":{"entity-type":"item","numeric-id":3978364,"id":"Q3978364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80323f1bcd6aa44173a2267ec08505c0c4723fc9","datavalue":{"value":{"amount":"+0.9151323","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":"Q1101239$33E92612-3AF9-4EB0-979D-54B69EBBBFCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df9059e37c00a34b5f041d095e4f70c189e53219","datavalue":{"value":{"entity-type":"item","numeric-id":3565954,"id":"Q3565954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cff1f0cf4fb1afa544adf878cd6a5f3e8e32621f","datavalue":{"value":{"amount":"+0.91487503","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":"Q1101239$00516346-24B8-403C-B967-7BCA34BEAAA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7155a6e4decfdd71db239f7a613c1cf32f786888","datavalue":{"value":{"entity-type":"item","numeric-id":3801585,"id":"Q3801585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f16d2fef0e37284fa7fd7242f3dbac5d785c2162","datavalue":{"value":{"amount":"+0.9147337","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":"Q1101239$D1662875-F6FA-4EA5-81ED-A0C8C8EBB9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6387c5dff0909ed45e880bbd9d2670a6681dad5a","datavalue":{"value":{"entity-type":"item","numeric-id":3708817,"id":"Q3708817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8a2ec122b5545a170040fa8a10b951a5c7041e7","datavalue":{"value":{"amount":"+0.9134476","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":"Q1101239$FF9852C9-EE0A-4EA8-9E94-F9D659B25686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95dd8895ce3d84a817ff1617bd313e7ef566d91e","datavalue":{"value":{"entity-type":"item","numeric-id":3004826,"id":"Q3004826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e0a92f01ba0b6ddcdec406085258e8129805420","datavalue":{"value":{"amount":"+0.9126137","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":"Q1101239$EEA73641-E832-4149-9820-B586CACDB794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3aeb96cf139cb702e41b7b167c597d03c8205559","datavalue":{"value":{"entity-type":"item","numeric-id":5500115,"id":"Q5500115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2254c738335c95171661f0dc003ee7ea18ec7774","datavalue":{"value":{"amount":"+0.90588033","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":"Q1101239$953361F1-A72A-4B70-A68C-69E50712171C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"516b9c925431127dd2bc4028614beb8866c07007","datavalue":{"value":{"entity-type":"item","numeric-id":1107326,"id":"Q1107326"},"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":"Q1101239$9895420B-8BEF-4B2C-86E7-AB4CA54FBF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba26b53fb155ab44342d1a786403bdaf32680e90","datavalue":{"value":{"entity-type":"item","numeric-id":5101871,"id":"Q5101871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35c2eb66bcd1ff3ae7a0b7295d1194938ffbcd59","datavalue":{"value":{"amount":"+0.90009177","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":"Q1101239$AA873430-8451-4522-BAA7-BEF9077ED263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5816451de3282f02d30c418411faf6f436ae2da","datavalue":{"value":{"entity-type":"item","numeric-id":942106,"id":"Q942106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c29ff59f4d5e90e3c7e6afcd09b837b9b9cd53c0","datavalue":{"value":{"amount":"+0.8978386","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":"Q1101239$D7AB3359-F34F-499B-BF1B-04A594086BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"203fccb10e25e3623c72d7fa667332864d60ac90","datavalue":{"value":{"entity-type":"item","numeric-id":2031165,"id":"Q2031165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d0c757d488bb2e5725fe68c2cf62a52cbdb53c","datavalue":{"value":{"amount":"+0.8948825","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":"Q1101239$FC3CB6F4-114C-43C8-8B32-105E2BFED55D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1101239","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1101239"}}}}}