{"entities":{"Q3745299":{"pageid":5775205,"ns":120,"title":"Item:Q3745299","lastrevid":50980916,"modified":"2026-01-16T01:47:59Z","type":"item","id":"Q3745299","labels":{"en":{"language":"en","value":"An O(2<sup>0.304n</sup>) Algorithm for Solving Maximum Independent Set Problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3980507"}},"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":"Q3745299$B1057C67-6BA7-47C9-999C-B4C286A9F013","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a931b9a3ee149535343805d4dd17758b1380ef71","datavalue":{"value":{"text":"An O(2<sup>0.304n</sup>) Algorithm for Solving Maximum Independent Set Problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3745299$1E31A998-EC71-47E8-8BD1-132D9002B3F7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07ce72f28c3da41c237cd44b43376d463d287f50","datavalue":{"value":"0606.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$ECF2F4B1-BEE0-4BFD-B817-85C0117F81FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eb0f9274797e63bb132265cc0accd6f3d6d04f62","datavalue":{"value":"10.1109/TC.1986.1676847","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$539281A7-1641-4C93-816A-D6751DAC977B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4eb77d1888db0dc862dde3a76d0f1f89bde8f54","datavalue":{"value":{"entity-type":"item","numeric-id":3745298,"id":"Q3745298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3745299$6083B6DF-97FF-4524-8BDA-9FACC2033E29","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cb95ba1181f89055fe808aa2c36bea9d3930d0fc","datavalue":{"value":{"entity-type":"item","numeric-id":80442,"id":"Q80442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3745299$6AD3982C-6CDA-46DB-8C8A-D7436C018FE1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q3745299$4B1A9A34-FC99-4B25-B30E-042D841B90C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$FE55C53C-1F74-4308-9D06-34C761303DAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$BF2F9276-B1A9-4817-9DC6-747B5A6DD99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$731293EA-BB54-49E8-A54B-EC43ABBEC8F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e962065ca6a34e46ce7cc8b2a9aef08e9c0e37cf","datavalue":{"value":"3980507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$A50ABAC8-5218-448F-A0D9-4BABB537BD80","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcdf6cf35d926c0daeb463f96c3fbb54af3858b4","datavalue":{"value":"case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q3745299$1EFCF22B-FA53-4C93-9987-6F9A29E3D2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8150c254fbd8520fb635963913f388e6e6da2545","datavalue":{"value":"deterministic upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q3745299$E55989ED-2F97-4723-92FD-F8DC24117189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3745299$C91895D9-B087-42A1-91EB-0096D0A90112","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"58146a20d0a63b308fe7ab303bb16f03e365258c","datavalue":{"value":"Q56210422","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$BA4EA0A6-B2CA-41CA-9009-7DDFADB67E9A","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":"Q3745299$BE699938-0620-4A44-9CE3-9642057B6C89","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"40918aa68baa7f423a66308f585151666f0fe38f","datavalue":{"value":"https://doi.org/10.1109/tc.1986.1676847","type":"string"},"datatype":"url"},"type":"statement","id":"Q3745299$772FC503-112A-4A83-BB1A-EE1DFDE840DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f8ac834423710fc3d324d0ab545247830db21b35","datavalue":{"value":"W1971756951","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3745299$89FDF9DD-27AF-40A1-84EC-CA9ED2699438","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c24a29e327c27dbf67ee97adafdd08c613070c4","datavalue":{"value":{"entity-type":"item","numeric-id":3777476,"id":"Q3777476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c36250c366bceba6a3f2819131851c9ee7af3e1c","datavalue":{"value":{"amount":"+0.8975566029548645","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":"Q3745299$C2EACD61-D9C8-414C-8007-82BCD4E6F2D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63c7a609912543429c21c20e755c12f507cdc496","datavalue":{"value":{"entity-type":"item","numeric-id":3525784,"id":"Q3525784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70f4e3568bbab2c7f11a24d384d7f84f496ad828","datavalue":{"value":{"amount":"+0.8830747008323669","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":"Q3745299$3637789E-2065-48F8-9174-DB27601D7E69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23f9710170281e2f38f0021bc2e94ec5894fa9f1","datavalue":{"value":{"entity-type":"item","numeric-id":2872097,"id":"Q2872097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5f24fc86e07894f3e9aff9636f5f31461193af6","datavalue":{"value":{"amount":"+0.8672102689743042","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":"Q3745299$22A10AA9-1279-4117-9396-54156F5D7ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d2d35fdc87d8f72526d95b25b390a7486532cc4","datavalue":{"value":{"entity-type":"item","numeric-id":2013558,"id":"Q2013558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52ea78e13cd38263f61c11332ca312637e960569","datavalue":{"value":{"amount":"+0.845786452293396","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":"Q3745299$6B482EE7-0CDC-48FB-AC98-A392FBD8269D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"342482c798308dcc94167036759d54eeea6a08e0","datavalue":{"value":{"entity-type":"item","numeric-id":3404455,"id":"Q3404455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bda4e0ff96e12e539eecf01ef0f846d1bac30b3","datavalue":{"value":{"amount":"+0.8434379696846008","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":"Q3745299$2E7A9AF4-0F23-413E-B6E0-699E87DAA6C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3745299","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3745299"}}}}}