{"entities":{"Q1261482":{"pageid":1272232,"ns":120,"title":"Item:Q1261482","lastrevid":47183881,"modified":"2025-12-31T22:48:56Z","type":"item","id":"Q1261482","labels":{"en":{"language":"en","value":"Approximating matchings in parallel"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 404994"}},"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":"Q1261482$0274CFB8-4E5D-4BA1-BEF3-9B0B597750DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"835fafed499e10f7b49df254f3b1258fa91eb88b","datavalue":{"value":{"text":"Approximating matchings in parallel","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1261482$6A337E7D-1357-40A6-B91C-48725853E0AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"224446877aacf54ff725367ab929c17475347814","datavalue":{"value":"0784.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$5DD715B4-FE2D-4E84-A404-D6D9C258C499","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"436b4ddd749b69a1544dad38a7dc169f040747f8","datavalue":{"value":"10.1016/0020-0190(93)90055-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$162DC915-A3BD-4A61-B0F4-B58EBA72BF71","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e66ee71689979a07fbda9f0299c5e5136616748b","datavalue":{"value":{"entity-type":"item","numeric-id":1261480,"id":"Q1261480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$B4FE1010-3660-4B5D-AACF-6F0549C14C92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"292ee0ed60d229834f4ba04d9e68598fca7e73c5","datavalue":{"value":{"entity-type":"item","numeric-id":536068,"id":"Q536068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$22CD77FF-3F67-4AAA-AA81-90D025911645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"652b8e8a879ea55b11d6d6a644a0b78a6d0bdf12","datavalue":{"value":{"entity-type":"item","numeric-id":1261481,"id":"Q1261481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$F47900C6-91A4-42FB-9C7E-F9119760B0E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7371aee48f8b820188fb929eb6be20f953a27e73","datavalue":{"value":{"entity-type":"item","numeric-id":689129,"id":"Q689129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$DD81244B-FFCC-4A1F-ACBC-EA6B676DE8D7","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":"Q1261482$C665ACFB-125C-49E8-A433-077CEBB42F69","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c4a0b6e2eb88a0201332122fd35e1ce2d966cc96","datavalue":{"value":{"time":"+1993-09-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1261482$B7228AC3-3F8A-4CA6-9057-ED78C160534C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e33bbde0d336a63c3bce7d2ef9a56393d196e24","datavalue":{"value":"A matching in an undirected graph \\(G=(V,E)\\) is a set \\(M\\subseteq E\\) of edges such that no two edges of \\(M\\) share a vertex. The matching problem is to find a matching of maximum cardinality. This problem is not known to be in NC (solvable in polylog time using a polynomial number of processors) even for bipartite graphs except in certain special cases; the best results to date are sublinear-time algorithms [\\textit{A. V. Goldberg}, \\textit{S. A. Plotkin} and \\textit{P. M. Vaidya}, J. Algorithms 14, No. 2, 180-213 (1993; Zbl 0769.68034)] and probabilistic algorithms [\\textit{R. M. Karp}, \\textit{E. Upful} and \\textit{A. Wigderson}, Combinatorica 6, 35- 48 (1986; Zbl 0646.05051)]. The paper under review presents another compromise: can approximate algorithm which, for fixed \\(k>0\\), finds a matching with cardinality at last \\(k/(k+1)\\) times the maximum in \\(O(k^ 4\\log^ 3n)\\) time using \\(O(k_ n^{2k+2})\\) processors on an \\(n\\)-vertex graph; with \\(k\\) constant this shows that approximating a maximum matching to within a constant factor is in NC. The model of parallel computation used is the exclusive-read, exclusive-write parallel random-access machine.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261482$BB9865E1-9C78-473E-8357-4EAF5700B014","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$1A6B23E7-DDF8-48E1-8A18-10054FC36EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$2DC4230A-920F-4DE9-9B79-F3BD2FD05C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$B03476A2-83CD-49FD-A4B8-3BB5776433A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$CF419211-3A35-495F-8C51-A266E391488D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d575770969f94d8e6d420296a1842c00f27594aa","datavalue":{"value":"404994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$B2D61EF4-B52B-4140-A3C6-F6F590EB2157","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f83f64c1c834e3af6b1baff0dfb711ad39e61c5","datavalue":{"value":"approximately maximum matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261482$3C3562CF-FA98-48C2-96A7-C6F9362342CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53f696ca55832c10e15749bb0744ba1a25e8de64","datavalue":{"value":"Nick's class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261482$A595A6DB-51B5-4C65-93BD-E1D35097A46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1261482$295A1353-9E0B-42B2-AA9A-5740B61F2B69","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$4C482160-CBF2-4175-8C78-778955BD19D2","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":"Q1261482$33EC2219-AB44-419D-9B24-F2228CF0D1BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$D865D8FC-DCAA-433D-A31C-0915C992883D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68168df6a65c7efc0077cf652fddf619a3b3d3fa","datavalue":{"value":{"entity-type":"item","numeric-id":4729373,"id":"Q4729373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$9496AAF1-2DC1-4CDB-B281-352B64901BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$8F200259-2818-461F-9B28-A6ADE651D8D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b712e361bbfbc97c265dcc3e2463de06c2cf58","datavalue":{"value":{"entity-type":"item","numeric-id":1103639,"id":"Q1103639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$C56B5F94-3B55-4A0C-8C5F-E7817A016ADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$0918A1AA-97A7-4387-8E69-A7B65FBAD5B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05f132c6521c12283446aaf341248df05dd5b786","datavalue":{"value":{"entity-type":"item","numeric-id":3904540,"id":"Q3904540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$A82B1D56-586C-4A2E-BEB2-B925249CA71E","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":"Q1261482$8D941B88-7EE4-4013-A0F7-61F6BF10406C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1261482$B1B7A760-464C-4A82-A382-120FC49A1E97","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f473a7cdd9fab9ae55448b77acdcdab4f5aed9e2","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90055-e","type":"string"},"datatype":"url"},"type":"statement","id":"Q1261482$884F8E4F-98A4-4CCF-AEA8-C64641AB2883","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"93c838c38241f59d913a496000248c6f081a44b9","datavalue":{"value":"W1998375300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1261482$6CE70E80-2714-40F3-A1F0-11E5C9734F1A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97e4c548b3015bd2b8ea9f758cb5d592990ca8d7","datavalue":{"value":{"entity-type":"item","numeric-id":294847,"id":"Q294847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd04bd021a98be03650adce275e22ced36f4b97d","datavalue":{"value":{"amount":"+0.883428692817688","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":"Q1261482$5BDA8055-66C4-4DA5-AA76-9F012A797794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa02114d804e4440fd8d5c3116696d397ac4103f","datavalue":{"value":{"entity-type":"item","numeric-id":845697,"id":"Q845697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70811f36645a28405f980cad7cf4f870bf63ab75","datavalue":{"value":{"amount":"+0.8743577599525452","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":"Q1261482$EC7A9A0A-9F69-455F-ACB8-F2CD5F8B6ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2bf5db8bac581eb60348cfb769dae5e339fec85","datavalue":{"value":{"entity-type":"item","numeric-id":4536416,"id":"Q4536416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d77c4591cc454c96d4a59ce3a7bbf6595e08bc1","datavalue":{"value":{"amount":"+0.8722573518753052","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":"Q1261482$F5666661-0086-4FAB-9330-56BF0C92CA00","rank":"normal"},{"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":"7f2840f57fae84114a2be04e481844e4ee2340bf","datavalue":{"value":{"amount":"+0.8653519749641418","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":"Q1261482$04F0F87F-D659-4637-B51C-FEF12AC30549","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":"a489b5d7fa370c0efde9a748af84586ece98fe74","datavalue":{"value":{"amount":"+0.8640714287757874","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":"Q1261482$4A96BEAE-CA8C-4859-A90B-7707452846FD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1261482","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1261482"}}}}}