{"entities":{"Q1262128":{"pageid":1272878,"ns":120,"title":"Item:Q1262128","lastrevid":68323065,"modified":"2026-04-12T22:56:18Z","type":"item","id":"Q1262128","labels":{"en":{"language":"en","value":"Improved processor bounds for combinatorial problems in RNC"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4123302"}},"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":"Q1262128$758CAC24-9D77-4ED2-897F-40B49AAD27F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"959e2466228c72290a868c0ce5fadac783c9447b","datavalue":{"value":{"text":"Improved processor bounds for combinatorial problems in RNC","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1262128$23FCF2AD-A178-48EA-8ED4-88E1E47E259E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6bc025986ab051170ae1888f4fb07eedf8ef21b","datavalue":{"value":"0685.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$49124DBB-7EAB-4793-8297-C26C2DBD4501","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d6d09870c234ebdb6cea6741cee218ecdbd265de","datavalue":{"value":"10.1007/BF02122800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$690F884B-6158-450E-842D-D83CCD5A1707","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$DBA40B62-A89C-4389-AB88-6F1BBBE3B3D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1262128$DD58F524-D8CE-4DBC-B33B-6E302390E803","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa11cc1ce0cf25903cabf5b4b278674791d72e15","datavalue":{"value":"A perfect matching of a graph G is a set of edges in G such that each vertex of G appears in exactly one edge of the set. The paper studies the computational complexity of finding a perfect matching in parallel. In (KUW), a randomized parallel algorithm of time complexity \\(O(\\log^ 3n)\\) that uses \\(O(n^ 4M(n))\\) processors has been designed. Here n denotes the number of vertices of the input graph and M(n) denotes the best sequential arithmetic time for \\(n\\times n\\) matrix multiplication. This paper shows that the number of processors can be significantly reduced (by a factor of \\(n^ 4)\\) while maintaining the expected running time. The new algorithm is a sophisticated implementation of the method used in [\\textit{R. M. Karp}, \\textit{E. Upfal} and \\textit{A. Wigderson}, Constructing a perfect matching is in random NC, Combinatorica 6, 35-48 (1986; Zbl 0646.05051)]. In particular, it reduces each iteration of the algorithm to computing the inverse and the determinant of an \\(n\\times n\\) integer matrix with bounded entry lengths. The improved solution to the perfect matching problem leads to more efficient parallel algorithms for several related combinatorial problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262128$4AF333AC-E648-4449-B3D5-589768F0D446","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$94AE5DBE-8EBC-4F07-95DF-A6B60739DF56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$4FFB9914-669D-4C8D-A4DF-272CABF621C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$C1A618B6-ABB5-4ECE-A0F1-B4EF34CFC89C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b8e47255b0483e2134dcfbcc7f83465c90760c0","datavalue":{"value":"4123302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$4A3156F3-7E07-447E-BC2D-1A8744D85728","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262128$460B7137-B14F-4505-82CB-4F3699F7CF28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"679372600590a03c48d4032113dc215d14bd33c6","datavalue":{"value":"randomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262128$3774028C-88AB-4FB9-8F61-D015E20FCDAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1262128$2C020A91-271B-44DD-8301-37A5C1E737C3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e427d06588e0f5e6a2a228b1ad8e00160bd43819","datavalue":{"value":{"entity-type":"item","numeric-id":673782,"id":"Q673782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$3A782931-DAD4-4D74-AE43-41B2F263BC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"748dce42a571924bd5dc5be9f8a70b8adc09d292","datavalue":{"value":{"entity-type":"item","numeric-id":163211,"id":"Q163211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$9FD92A62-89E1-4083-9149-4A1BED5C589C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"adc03b8d65b7e3a67e4169bd1cb14298d90ff1bf","datavalue":{"value":{"entity-type":"item","numeric-id":170469,"id":"Q170469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$CD60C6FB-6625-4531-8A2D-7D84180800FB","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":"Q1262128$DC6869EE-1D0E-48EE-A989-2F6432EB894F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"33c7a78759148ce6b1abced42ef4a952f4334dd8","datavalue":{"value":{"entity-type":"item","numeric-id":794429,"id":"Q794429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$58294E0E-7739-4724-88D8-FF8D2036E424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb5037acc3949cbca8f8e77ab83b58c3f57e4b13","datavalue":{"value":{"entity-type":"item","numeric-id":3732965,"id":"Q3732965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$D7C3A64A-D618-4B59-8C9F-FCD69DB24EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6b13b2ba37a9810801d8784e6422607a5338cc","datavalue":{"value":{"entity-type":"item","numeric-id":4745254,"id":"Q4745254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$4A93C4FA-2216-4599-BB1B-0B0126CA9CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480ac560f713e57a5ee8cd072f59d2635f9c43d4","datavalue":{"value":{"entity-type":"item","numeric-id":915378,"id":"Q915378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$4C039178-1F92-49AE-9B6C-4671ABAE4820","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e627512a063f8909b9161f05ca4719139a48cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5331504,"id":"Q5331504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$185E39F5-0429-44EF-9C19-5977CC7DF5EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec62482a6f1abfd15d9d0aa6d0ca02f4b7a14835","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$3A4AF9FC-A775-46E3-9930-DC299E2497E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f6d49f34b90554bdc2124202c77c3ea514e0173","datavalue":{"value":{"entity-type":"item","numeric-id":1244782,"id":"Q1244782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$89831CF8-0624-4119-B4C0-4561C2A6ACC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4ab13142076117cc14856c9cfe9c081eaaa2f9d","datavalue":{"value":{"entity-type":"item","numeric-id":4172915,"id":"Q4172915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$EF109F09-1B6D-4FB0-89A8-73DFB6CCF194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1262128$5B1E118D-601E-443D-B349-51840781159F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"49e4e901e37f2e0a920e1f29f853fb4ee81a837b","datavalue":{"value":"https://doi.org/10.1007/bf02122800","type":"string"},"datatype":"url"},"type":"statement","id":"Q1262128$AB86CE76-DBF0-4B64-AF0D-FAFD2EC85E59","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"941fd2b726465a1b11106def5cc74c4ae1207226","datavalue":{"value":"W2040699536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1262128$B0D827C2-D17C-4C54-8EFE-D1F2D0EBADBC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"460159613a58e18198314080025c89695b6628d8","datavalue":{"value":{"entity-type":"item","numeric-id":2471700,"id":"Q2471700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"765da0828e46f56bdedd36704d638d9c3f8e859e","datavalue":{"value":{"amount":"+0.8693563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$79C05209-FC30-48CE-898E-2C66EC8E874C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2723f215a12e6e020b5f81301e2495a15ef9fc05","datavalue":{"value":{"entity-type":"item","numeric-id":1261482,"id":"Q1261482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31cadc22731bac508c8acc6c4b5a6d92276acedb","datavalue":{"value":{"amount":"+0.8420855","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$8F52B018-BA97-4803-9BF2-DD6FF22FE27F","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":"b857598bc46472c1671d879e1dfd14d537a5a9a4","datavalue":{"value":{"amount":"+0.84081364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$6F98DF0B-3AC2-4741-A58C-98F73D9CD320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d4e65e7063e3a828b4a518dc1ac05dbe313585b","datavalue":{"value":{"entity-type":"item","numeric-id":4389326,"id":"Q4389326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc0efce15b082db07c237a7f6533bc5b85d17e2c","datavalue":{"value":{"amount":"+0.8395066","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$A1E9AA11-F951-4DD7-8D17-AF202DEBA7C9","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":"fb672c8562be84dc5b674e56d2b30fd561e8b244","datavalue":{"value":{"amount":"+0.83461946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$83944991-37B5-422A-8999-8C89A334EC66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ddcd3242f7e86d482a94717da2347b20f91626d","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d083a870c6d9e45f67fedb5beaa11a69c3d8deb","datavalue":{"value":{"amount":"+0.83065116","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$C795BFD4-5231-46A3-B07B-F409392BC2F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20ae50856b394811b8089ac5efbb3d98828706cd","datavalue":{"value":{"entity-type":"item","numeric-id":5132024,"id":"Q5132024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"538691a9d331aa25fb6bd5089c25d678e07d522d","datavalue":{"value":{"amount":"+0.82464755","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$39952890-D3BA-41E8-8EF4-B7DE7BD17272","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":"8afa711dbb98c60a8e0cc1c5f8614cb8bc2145a8","datavalue":{"value":{"amount":"+0.8209187","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$1068E884-D92A-42AA-8ADC-CD3AEAE47949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"443f606f1e6cadb2ffc410644aef2aa9940e9941","datavalue":{"value":{"entity-type":"item","numeric-id":580373,"id":"Q580373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"449f9e366c8ab6026137ed2c85e833597db82a28","datavalue":{"value":{"amount":"+0.8208952","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1262128$6C933915-D662-4741-BFB8-CEE48BF51ADA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved processor bounds for combinatorial problems in RNC","badges":[]}}}}}