{"entities":{"Q3768419":{"pageid":5798325,"ns":120,"title":"Item:Q3768419","lastrevid":51868331,"modified":"2026-01-20T10:42:53Z","type":"item","id":"Q3768419","labels":{"en":{"language":"en","value":"A fast and simple randomized parallel algorithm for the maximal independent set problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4026849"}},"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":"Q3768419$B05FE1FE-EAA6-480E-BD59-5F3C0A4B8B8B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a4939aa95a1837a5b674824cd89cbf2a1716b301","datavalue":{"value":{"text":"A fast and simple randomized parallel algorithm for the maximal independent set problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3768419$0D788C10-BD08-4A98-8808-FA18AF645166","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fcab1a72385d84857c704aab566c2de8a60f7c30","datavalue":{"value":"0631.68063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$066CF878-8BFD-4ED0-894C-329D1C99748C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6dc7d4b053a8e0dff28b3f0b58d325c2743bc2c","datavalue":{"value":"10.1016/0196-6774(86)90019-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$FAEDFFDF-8D56-4343-AA5E-9F3E2B37EF80","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3768419$F2F0DAB9-5ABA-49B5-B5F4-12B212BE9B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb810284579fca70d13987c395247bb8f287f16c","datavalue":{"value":{"entity-type":"item","numeric-id":196035,"id":"Q196035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3768419$B4AD9E01-8FFC-4E0A-ADB6-BB7BB314D9E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"768e033f31190cbaea0944ac118f8a6cb545c066","datavalue":{"value":{"entity-type":"item","numeric-id":294682,"id":"Q294682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3768419$5FD85B81-CF71-4D2E-B112-BFD6A8CB03B8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3768419$8FEBB664-387D-4DA7-AC26-A599C5C79F2A","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":"Q3768419$18EA0266-B807-4072-AF53-E6B26FCA5E30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$8704D2CC-D06D-478A-847D-992A59875DAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$4E2216B5-C180-4E67-86B1-6600F0A50E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$5CC56CF9-671A-45BC-A023-D8C587859BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$33C1CD5B-4FE2-4ACC-B639-3DBEE5965BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$8E53F507-8D80-46B6-B205-CA1EE30D6AFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$1590A89D-E489-42C7-844B-9DD29AB68814","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1f517d3310de9d62d6662fe0ef0c2cc003eb42f2","datavalue":{"value":"4026849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$9182BDDC-1ABF-429C-A1C6-A2412BAAA05E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f37e862a1875c3cf3e89d1e157211199441f10bc","datavalue":{"value":"parallel randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q3768419$4902E430-97A0-4251-97F2-3CA0B4660F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b1c9b5c3efa1764ae3fc9794c3bd2cb77131717","datavalue":{"value":"maximal independent set in a graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q3768419$D5E44B3F-8895-46AE-8E59-BD0DD475CFB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a38cdf8c3160fb2b36f6fd0d516fc65074d451e4","datavalue":{"value":"expected running time","type":"string"},"datatype":"string"},"type":"statement","id":"Q3768419$200AB0D2-0E31-444F-8C02-FCC860EB3F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"072bf6ac713e057d48099035ac6b50794ee192a8","datavalue":{"value":"concurrent-read concurrent-write PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q3768419$9E64AAEC-1A0D-471F-9E22-CAAB6742C868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b20f99cc680851792cc019f340ff6d830d0a950","datavalue":{"value":"exclusive- read exclusive-write PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q3768419$EC40917F-E71D-4388-AEE5-B72755BB0325","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2c5538e5126fca484d6cca9b9ef058ccb8153ee4","datavalue":{"value":"Q29396733","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$68519CD3-AC25-4B53-823C-FFA22AA04B66","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":"Q3768419$FBC7CC37-4AAE-45E0-9F13-75B8AB8D9A35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0a4dbda9e509f4216d195aa99a0a5ccf7c2764ec","datavalue":{"value":"https://doi.org/10.1016/0196-6774(86)90019-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q3768419$8EB17449-20AA-4171-BBCD-EA3A3CC0F954","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dabaa9c40cbcec52aa60cb2bec4d2a721b82fa2a","datavalue":{"value":"W1964089073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3768419$F00B7AB5-F504-4574-8365-473B441FFD78","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a453761894a408c2632741908bd24f2fc41a00fe","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0035d906e283fd8efb08f8577f263c1b9023acf","datavalue":{"value":{"amount":"+0.9315927028656006","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":"Q3768419$2DA2DF56-450F-4208-B615-29E7AEF14316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ece252943494c02f3a371f6943ed81e32f10e5e","datavalue":{"value":{"entity-type":"item","numeric-id":1318767,"id":"Q1318767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87c618c3b618761a49468220f19a721a8f8472c4","datavalue":{"value":{"amount":"+0.9183436632156372","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":"Q3768419$3D3FA500-C36C-4EEE-A2D4-65F1F4921F10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57f07974b09b2e761942819e55d60d3006fd976","datavalue":{"value":{"entity-type":"item","numeric-id":913519,"id":"Q913519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57ce9590ef17d853443ab4daefbef83a5ab11c6a","datavalue":{"value":{"amount":"+0.9161403775215148","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":"Q3768419$8D3DB4ED-4C0E-4E50-ABE5-4F25E3999090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad24f8b4046a59c89cb8d1f22be46302f90cf4fa","datavalue":{"value":{"entity-type":"item","numeric-id":4729373,"id":"Q4729373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c3fb55a899f8d55ece7f0b72b83c72b457e1265","datavalue":{"value":{"amount":"+0.9081496000289916","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":"Q3768419$FD9BFE6F-5A8F-4DF6-88B3-D15985F06CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61c9ad9df7362f21c2ecc04c53a766c54989fbd9","datavalue":{"value":{"entity-type":"item","numeric-id":3756533,"id":"Q3756533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fbe22c47640b0cded607a68107f3d00d9bf7697","datavalue":{"value":{"amount":"+0.9025437235832214","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":"Q3768419$AC99881E-BFFE-4FF8-88CF-8D7D027A002E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3768419","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3768419"}}}}}