{"entities":{"Q1073573":{"pageid":1084325,"ns":120,"title":"Item:Q1073573","lastrevid":48917458,"modified":"2026-01-06T04:28:30Z","type":"item","id":"Q1073573","labels":{"en":{"language":"en","value":"A fast and simple randomized parallel algorithm for maximal matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3945362"}},"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":"Q1073573$096C6D4B-8BA2-41D3-81FE-B23585043892","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7d81429d6d0d5109b2d0aadfcc221649d1c9b079","datavalue":{"value":{"text":"A fast and simple randomized parallel algorithm for maximal matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1073573$32595D49-8C56-453C-BACA-3220BCD835B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f2968bd19117ce273aa54d5ca2fb8724fe1bc0f","datavalue":{"value":"0588.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$64D67DE8-0AE1-48D1-AAB4-D82640A42DDE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec0cb391641f5dc9888e080f1c32f20a540b46ec","datavalue":{"value":"10.1016/0020-0190(86)90144-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$9300BAB1-1196-4D32-B6A3-DAAAA6C5E269","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a026775bce3c071e93242df2b7eae0d424cc6513","datavalue":{"value":{"entity-type":"item","numeric-id":293173,"id":"Q293173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073573$EBD3C919-0EB3-4B12-95C4-BFA427A3B7EE","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":"Q1073573$741DDB3F-500B-450C-9299-F5836536B626","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073573$F0F6D5F5-4C3B-44A1-8CD3-9A48DAFD119E","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":"Q1073573$666DEB03-94D1-41A2-98A7-F9BE621D54EF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4c5303808f7be2b65e743fefbdea4c6a727ce428","datavalue":{"value":"A parallel randomized algorithm to find a maximal matching is presented. Its expected running time on a CRCW-PRAM with \\(| E|\\) processors in O(log\\(| E|)\\). The expected time is independent of the structure of the input graph. This improves the best known deterministic algorithm by a factor of \\(\\log^ 2| E|\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073573$6CFB9D30-2C66-4DB6-A2EE-9C5089E58F7E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$4191E727-4F96-4B7F-BD3B-1BF2C5AFF154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$FE318CBF-1FBD-42E2-8941-69B20A0E1274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$917CB0B4-1B13-455B-BF9D-F0BD116E9814","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b9f5910a5775b3eafd76ac0134360c1e80831a50","datavalue":{"value":"3945362","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$D17C9AF8-495A-4716-B5A8-1BA631304E64","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073573$1F9BC56D-180D-4EE3-AA34-19C7D5249F3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f37e862a1875c3cf3e89d1e157211199441f10bc","datavalue":{"value":"parallel randomized algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073573$249AA99B-0232-481B-9730-69078726AD69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0a5168ba03b01930dca9d664be03b3d700d0951","datavalue":{"value":"CRCW-PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073573$BB12441D-1E36-4215-879F-5F3F01EEE5DD","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":"Q1073573$52BFEBC9-9A34-4983-8A86-BD2451071AA5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d0d1cd97cca3fb2fd05c4da28a79f95aeb86b2d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90144-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1073573$2A4A92F5-4743-4D15-9C0F-55FC2D47FFDA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9af999a16a4f41062025325d7043e0a890716541","datavalue":{"value":"W1964932074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073573$9DA06029-DA3C-442E-97E2-E3BC02B43071","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a8b9e919631fd13058b126b3a76e6cf944e4f8e","datavalue":{"value":{"entity-type":"item","numeric-id":1073571,"id":"Q1073571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073573$6A7E2BAA-30AF-411F-BBDE-541FB41578E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3e32cd00e50889ce6fdac19be614a9be1a54020","datavalue":{"value":{"entity-type":"item","numeric-id":4164569,"id":"Q4164569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073573$5733F6EB-FA09-4001-A096-B3898FF96450","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a9fb282a36611bb3cbada3d8d6a65b98e395072","datavalue":{"value":{"entity-type":"item","numeric-id":1073571,"id":"Q1073571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce5678483b2909092b0f2e12ab606d816dc3c256","datavalue":{"value":{"amount":"+0.9279818534851074","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":"Q1073573$6FC6712A-15FA-4D32-9144-B621A8603AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ceff47858bf06fc5f9a01de6d31a1e4c75a2e73","datavalue":{"value":{"entity-type":"item","numeric-id":1341686,"id":"Q1341686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e4dca0ee108db07d8c35c23f722a297374574f2","datavalue":{"value":{"amount":"+0.9200050830841064","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":"Q1073573$E38F991D-405F-480A-B285-FDC16E1E97E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f045dd2957111ad39dec15e9f19e85deb0da14b3","datavalue":{"value":{"entity-type":"item","numeric-id":672837,"id":"Q672837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99393579d89bb46f487043f9f7b2184a95744eaa","datavalue":{"value":{"amount":"+0.9186559915542604","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":"Q1073573$519F190B-652D-47C0-8726-36750A3637A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42fa5429f49f4f8f9ba71df4ca66a9d0aaf506fa","datavalue":{"value":{"entity-type":"item","numeric-id":4489037,"id":"Q4489037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0d6bc4edcae78320992e8e8d90bcd0d7e219015","datavalue":{"value":{"amount":"+0.8974489569664001","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":"Q1073573$BF38341C-4812-46D4-81F1-D33E82481E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48d9a0289a755c4270288c0a69bdf1bbea7e5aa1","datavalue":{"value":{"entity-type":"item","numeric-id":1352118,"id":"Q1352118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"447366a177dc96fe2b9e8ef46a047656a540ec30","datavalue":{"value":{"amount":"+0.8847417235374451","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":"Q1073573$899B359C-5DAF-41D4-9282-BA93853AA890","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1073573","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1073573"}}}}}