{"entities":{"Q1073571":{"pageid":1084323,"ns":120,"title":"Item:Q1073571","lastrevid":48917455,"modified":"2026-01-06T04:28:30Z","type":"item","id":"Q1073571","labels":{"en":{"language":"en","value":"An improved parallel algorithm for maximal matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3945361"}},"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":"Q1073571$99DAC4D5-AEB4-476E-BBC7-0168A356E620","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7448ec8614d153ce89926fda31b3851a6ac17aa3","datavalue":{"value":{"text":"An improved parallel algorithm for maximal matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1073571$C353CBB1-A7DF-40DA-AA24-AA5E03B78BDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8053fe6ce71249ee46e6b1cb42e3de21f14c150f","datavalue":{"value":"0588.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$D1FDA71D-26B7-4EEF-B367-941C051F841D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"49ec25a09186f57df20d35a934564c532fb36636","datavalue":{"value":"10.1016/0020-0190(86)90141-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$6F6C6244-8948-4C57-AF2D-9132F48DB79B","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":"Q1073571$1DA062F0-2BAA-4F02-8298-1D658BFC6E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4bd9098e307c0d203e127f6e8054da1a54d577b1","datavalue":{"value":{"entity-type":"item","numeric-id":1149226,"id":"Q1149226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1073571$24E1C30D-E5BF-43DA-9989-DCD4400DAF2E","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":"Q1073571$04DC9571-3DA7-4812-AC60-98F9AC12166A","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":"Q1073571$7ACB82C4-D5D7-4E21-BDFA-6C761CBD8DCD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe1f1e3d4fc1d4a47cae58b7efd28498ec7c24ba","datavalue":{"value":"A parallel \\(O(\\log^ 3| E|)\\) algorithm for finding a maximal matching in a graph G(V,E) is presented. The model of computation is the CRCW-PRAM, and \\(| V| +| E|\\) processors are used. This algorithm is a substantial improvement upon the two previous algorithms known to us. These algorithms by \\textit{R. M. Karp} and \\textit{W. Wigderson} [Proc. 16th Ann. ACM Symp. Theory of Computing, 266-272 (1984)] and \\textit{G. Lev} [''Size bounds and parallel algorithms for networks'', Tech. Rep. CST-8-80, Dept. Comput. Sci., Univ. Edinburgh (1980)] achieve \\(O(\\log^ 4| E|)\\) depth with \\(| E|^ 3/\\log | E|\\) and \\(| E| +| V|\\) processors respectively. The last one though having a better performance than the first, only applies to bipartite graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073571$33DA0DAF-935C-4493-99A4-2659103CF288","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$A8EC9DE1-D754-465E-9280-F878EF42EFED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$A46C59F3-C4E0-434C-9DC3-5976AFCBBEDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$180A0F88-6F9B-4388-AD2A-B15C4ACB77F7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"90a2006cf57f24f9a3ab729d47e5c34c5b320df1","datavalue":{"value":"3945361","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$D2C7DA70-CE3D-4DD2-BA7A-8EAE05069D7D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073571$C5C21211-C800-46D8-AD2A-B25B02A9452B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0a5168ba03b01930dca9d664be03b3d700d0951","datavalue":{"value":"CRCW-PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1073571$14EB29BE-3549-4A64-A603-DD21BAA23A20","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":"Q1073571$2BADCB92-5555-4CD2-98F4-FEA11DE69F27","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e70c5df8e0d9127e5b389dc45ff0a8a2432e9da5","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90141-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1073571$46979F4F-AC5B-48A7-8D8E-F527385C83B5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"655577dac005011b9cda2a18834d0553a8961de6","datavalue":{"value":"W2073975876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1073571$7C16CB83-E859-4E15-900A-5FFA2830474B","rank":"normal"}],"P1643":[{"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":"048bb034ced73d41f6bf9541cec433f5d6bd5eaa","datavalue":{"value":{"amount":"+0.9518795013427734","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":"Q1073571$0BD9D05A-B143-4B93-967A-B6F68355E66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3de33ddf4fd4589d6a70adf0c100cf089e4a408c","datavalue":{"value":{"entity-type":"item","numeric-id":1288436,"id":"Q1288436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a6c0134dc59538f4eeaa301aa42487c41c22f06","datavalue":{"value":{"amount":"+0.9500513076782228","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":"Q1073571$48935F2F-8B08-4534-A8F2-C45F8BBE8C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91f39a0f9005943790e7f4148d58e586fce7e88a","datavalue":{"value":{"entity-type":"item","numeric-id":1073573,"id":"Q1073573"},"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":"Q1073571$2C5173B5-2688-4179-8DD8-2CC8BFC949FF","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":"16f988a29d02c417fcb3274b6d7f689e70d71def","datavalue":{"value":{"amount":"+0.923973023891449","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":"Q1073571$1038609A-CE1E-4D92-9193-1E930E7885FE","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":"616db861b59fc8f75ecc29cb76d522823dd8e005","datavalue":{"value":{"amount":"+0.913797914981842","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":"Q1073571$A37FF5F2-A0AB-46EF-A36A-39EA3A0CAC46","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1073571","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1073571"}}}}}