{"entities":{"Q5361909":{"pageid":7391483,"ns":120,"title":"Item:Q5361909","lastrevid":96102323,"modified":"2026-06-05T10:25:09Z","type":"item","id":"Q5361909","labels":{"en":{"language":"en","value":"A Distributed (2+\u03b5)-Approximation for Vertex Cover in O(log\u03b4/\u03b5 log log \u03b4) Rounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6784148"}},"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":"Q5361909$AB9A4428-0E05-4DC2-A8DA-69FFA72EE36F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3761af0bc1510787a95448257ba0311240a10f0a","datavalue":{"value":{"text":"A Distributed (2+\u03b5)-Approximation for Vertex Cover in O(log\u03b4/\u03b5 log log \u03b4) Rounds","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5361909$91BA75C8-FA10-4428-AE6F-1AC1DBD099D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7be9f6a7a9a20ea345d39e138ba7ebafda630b93","datavalue":{"value":"1376.68155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$67283EB8-8692-484B-B620-8DCA2BA50B22","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a5f5e2003c9b341d15180a76df89bda72e8e56d","datavalue":{"value":"10.1145/2933057.2933086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$DC42467D-6698-4289-B231-B853E7C8CE7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"50169214229f0aaa4dd9bb9948faad51feef1744","datavalue":{"value":{"entity-type":"item","numeric-id":259273,"id":"Q259273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5361909$81E7190A-722F-4F59-972C-9FC31AC35DF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"942b0610b67df1beccf57dae3ae6530918c3fec8","datavalue":{"value":{"entity-type":"item","numeric-id":1660918,"id":"Q1660918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5361909$79C9EF10-8519-4775-80AC-0903CC824BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"91cc9aff8aea71118d3c150b25b82597f27b210a","datavalue":{"value":{"entity-type":"item","numeric-id":1130167,"id":"Q1130167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5361909$DFB33D40-2507-45BD-AFD4-583FF1E4657B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a144f60a976d9adee5b526bc3e03607b9cb8ec26","datavalue":{"value":{"entity-type":"item","numeric-id":5361908,"id":"Q5361908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5361909$2358A5A3-48B4-46C5-920E-F5D2083DFF00","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"38c6a695cf3837fb6c40a9b0aaa4c3b6a2324244","datavalue":{"value":{"time":"+2017-09-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5361909$14494E36-6792-4B74-8348-FCE8C2C18048","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd3a1ca635e04e1daae3fcff9deb39b385111dc5","datavalue":{"value":"https://arxiv.org/abs/1602.03713","type":"string"},"datatype":"url"},"type":"statement","id":"Q5361909$BA3A6827-8194-47A3-BD96-58B3E4EE4F4E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$A62CBB39-2C0E-4700-8E22-2F4B14FA1B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$950AD600-D02B-40AA-91EF-7BB8E0655769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$B6DF8970-2353-4BF0-8934-517A991252DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$D40949F4-18F1-443F-80A5-6A341E1C68EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$0ACD4660-DE3D-47C9-8C64-765A6DC9A023","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e89f353e8d5b14462bc836b24814a2aaad669ae","datavalue":{"value":"6784148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$D96E4EB8-E7C5-4F3D-9F61-32C2D84095F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5361909$A40FCCF3-E92B-4456-BB28-3CF6BF1EDF73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b8c6c097f0d2daba5381878b194a97cc0311938","datavalue":{"value":"distributed graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5361909$9A3CE35A-7DEB-4F93-9A57-DBFE857F5138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00db6e22815c393ebea4e28db56f3df041d11dd6","datavalue":{"value":"local ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q5361909$8A7B95FA-9DE0-4834-A273-850A0CE29268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q5361909$36B85B08-251A-485C-BEBF-B9500EB41B13","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":"Q5361909$BB2EFE1E-12F9-4B7B-BB1D-F76C9D19EF16","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"753955809e99832fc03d1681e7a8c42a50e93006","datavalue":{"value":"W2403340448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5361909$E890CE33-7CAE-47CB-8D93-54506C592A2B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6fb62eb5b2008d09bb65ed0a3609000afb1d99e","datavalue":{"value":{"entity-type":"item","numeric-id":4640294,"id":"Q4640294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23a25b5712d1217de0eace9e152b29261e717fbb","datavalue":{"value":{"amount":"+0.9991294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$8765C123-D7DB-482F-BA04-D014C4B920AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b882f42283f96540dc8a600c4eff624b8f05787c","datavalue":{"value":{"entity-type":"item","numeric-id":1713914,"id":"Q1713914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af5f163086ccf753e4b19aa6ca7c607a2ef13528","datavalue":{"value":{"amount":"+0.959007","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$E6E611D3-E62A-4BDE-9CE6-4A0FBD1D9667","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"008ffb7ec9505857ff7700db4017ec3018991cfe","datavalue":{"value":{"entity-type":"item","numeric-id":3578307,"id":"Q3578307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f40df5f62dea3f1ade7a197a923c1489a049fa25","datavalue":{"value":{"amount":"+0.89971906","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$10340562-0BEF-4058-AC01-74CC11529390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b357ba20c0f6b2a08e9360613d905fef38f31d9","datavalue":{"value":{"entity-type":"item","numeric-id":4608050,"id":"Q4608050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c47c0a0b303ec0ef6199f374529d6703516297e6","datavalue":{"value":{"amount":"+0.8951143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$D714227E-ADC0-4754-85D7-380445FCE3E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60a75496d314bf5569ecb846f4a9217ab8f520b7","datavalue":{"value":{"entity-type":"item","numeric-id":5236297,"id":"Q5236297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdb9e0b4cfe57277440aad9cd85e01e3850a9ff1","datavalue":{"value":{"amount":"+0.8912285","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$5FF7A78B-E20F-413F-BFD0-2030274C08FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6dfad8732709dd59e893bde6d1acc5cabe10944","datavalue":{"value":{"entity-type":"item","numeric-id":6179658,"id":"Q6179658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f36d4efd1b142da6d5cd21f59a8a31cf297b8b68","datavalue":{"value":{"amount":"+0.8814292","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$C068957F-F84F-43FB-84D0-D24BCB521AC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"976d3419fc288cff8a9d99f7fb88d823be9f9671","datavalue":{"value":{"entity-type":"item","numeric-id":4344228,"id":"Q4344228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1141c9713d58096452ee993d0ec90ef43b46c424","datavalue":{"value":{"amount":"+0.8733029","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$8D0CDEFE-0693-466A-B815-37A3EAD46B77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4134fbcecce48c03f23e96ee8a4892caaee1fe78","datavalue":{"value":{"entity-type":"item","numeric-id":2712300,"id":"Q2712300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16de2ade48092a2a3c32ee90d4341852b2f9458b","datavalue":{"value":{"amount":"+0.87296426","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$1C037F39-5B64-434A-AA5F-A31B28B9AC6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22f3497684b107a30cb18a2736ec9185757043b7","datavalue":{"value":{"entity-type":"item","numeric-id":3578370,"id":"Q3578370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e503e02f9ec336c5d843902b51151ac7ccc1b6a4","datavalue":{"value":{"amount":"+0.87077594","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5361909$76C27403-0AB2-4BB0-AD1C-3B23F4BEFB2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A Distributed (2+\u03b5)-Approximation for Vertex Cover in O(log\u03b4/\u03b5 log log \u03b4) Rounds","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_Distributed_(2%2B%CE%B5)-Approximation_for_Vertex_Cover_in_O(log%CE%B4/%CE%B5_log_log_%CE%B4)_Rounds"}}}}}