{"entities":{"Q3177774":{"pageid":3188484,"ns":120,"title":"Item:Q3177774","lastrevid":58130529,"modified":"2026-04-03T22:38:44Z","type":"item","id":"Q3177774","labels":{"en":{"language":"en","value":"Local computation: lower and upper bounds"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6912613"}},"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":"Q3177774$7B5BBC06-CDA4-4181-98EC-51FDAE40FF75","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"572094126fa6b3b964288ae9c3058a5039b0b7c8","datavalue":{"value":{"text":"Local Computation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3177774$25EE9B91-3E3F-41B7-8712-E6DE05BA6616","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"132249f36eefe729d86195797fe5dcabd37ef7c2","datavalue":{"value":"1426.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$60491FA0-41E8-4142-A2F3-DACF65A03C39","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"40767583efaf367ae1d1764e01564e6155db5fac","datavalue":{"value":"10.1145/2742012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$68B96FD2-451C-484E-86C7-42F2DB59C7FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"774beed7b4ed7ed23547248beae25fee7b709737","datavalue":{"value":{"entity-type":"item","numeric-id":613112,"id":"Q613112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3177774$B3E84A21-0E55-4403-B578-D1042DB363D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8f6e4f78bf499b0fcabd7ab393cf908821074480","datavalue":{"value":{"entity-type":"item","numeric-id":251291,"id":"Q251291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3177774$ED105A9B-7F72-44BA-9BA5-39752F9F2831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6326f08d101e08bdf835ef63dd1fab6d72f29ad","datavalue":{"value":{"entity-type":"item","numeric-id":249057,"id":"Q249057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3177774$A7FBF95D-6150-4FB7-9CB4-98445DECEB24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f12bfc80fe4a431c556e028f5134a217234a7cc4","datavalue":{"value":{"entity-type":"item","numeric-id":63915,"id":"Q63915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3177774$740B2B90-FE7E-479C-8D9B-E19160C5D6CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a9aa22cb8a96ecb8781adebec8cb26e1601a98e8","datavalue":{"value":{"time":"+2018-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3177774$31FAFC6F-79B8-4571-B8F8-73CA69255A6D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c0a6183fb4ba1f05c8cf1f181e6fe68e8f2d199","datavalue":{"value":"https://arxiv.org/abs/1011.5470","type":"string"},"datatype":"url"},"type":"statement","id":"Q3177774$533DC028-F75C-4173-8DC5-C6568B7B0878","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$DB62985A-8E90-4BFC-AC9B-1DA40C1F7D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$12BDDA71-1A87-463C-B172-FFEC836545BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$BCB47BE3-62C4-4D87-B551-F4D609B4C11E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$142ECB98-CFD6-40A3-A849-82A4123D6F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$328F5724-C86A-4E0F-B39B-CD260FC174AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$0599F2C7-5ABC-4449-8E8B-F5FD752CFD48","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"593fd4e53a90a56f72dd6578f3c33a9a952b7d30","datavalue":{"value":"6912613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$29F6B520-054A-4395-82A9-6C3AB9FFF4CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e6f2842ba16618da57de12b4c27b4274e41c364","datavalue":{"value":"approximation hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$4C1BC92D-B5E8-4B4F-85C1-6FAD45A37405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94b7a26ad84bd89709cc5d23472ced17cefeabec","datavalue":{"value":"butterfly effect","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$2B0C215E-7D0F-46EA-B4CC-7A3260E13C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387e204c6977d7b097ac93bf9a6ecf723e21df10","datavalue":{"value":"distributed algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$B70A9280-A916-4FC5-AEAA-F60F414C102D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$748848C3-8800-45D4-8AC0-847CAD59799D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d5b73a08163a09a75cd91878ee7b2e9cf204284","datavalue":{"value":"locality","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$5CB45650-1871-46AC-BE3A-D0B03F1BB696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$A9FD9498-86BA-42F2-AE10-34E53ADA4EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ae5cad662cee9457a0e88de5ca640ccabb9ba00","datavalue":{"value":"maximal independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$5E18101D-0F4E-42A9-8338-89E71703578A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4621396570425e2b0396722014057849131f6c8","datavalue":{"value":"maximal matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$76B17EA9-B751-4355-8EC0-514C130F97F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c8c7d43e68a09ab666821c7b19ecfe8220feed6","datavalue":{"value":"polylog-local","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$619F5846-2BE8-4343-A568-87EEE9AC17F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q3177774$827FE1D2-B6D1-4874-8B05-610A42C8755B","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":"Q3177774$211ABFEE-7196-43C7-B33E-BB7246396625","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e69c94000d8d900807787ac35c4d4a524d73800e","datavalue":{"value":"W1957963525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3177774$75CA5857-BE32-4622-B478-417FA0A26641","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fa31673ae40df17e458cc804f512a1f6fb0fd68","datavalue":{"value":{"entity-type":"item","numeric-id":5501510,"id":"Q5501510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40f76385ab52cfd9fe91dade1aaae4bbb7d6ca77","datavalue":{"value":{"amount":"+0.8719803690910339","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":"Q3177774$8F1539F4-DD27-42D5-A56B-2AB0EE07A7A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ddc909d73054c5f4f1bd20bc4640510ad9a3858","datavalue":{"value":{"entity-type":"item","numeric-id":4862796,"id":"Q4862796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"badc93f8b54da2fb7777801ff89363953a3ac86b","datavalue":{"value":{"amount":"+0.830467939376831","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":"Q3177774$09F17FB1-EFE2-47A1-B47A-B51FB88536FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b401aa13243ea438dfe244c1a56689bc6411a8a0","datavalue":{"value":{"entity-type":"item","numeric-id":5395731,"id":"Q5395731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8790103815beb105b1ff004cd2c295740169ecba","datavalue":{"value":{"amount":"+0.793576180934906","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":"Q3177774$98D4208B-CF28-4FB1-9163-72A3806DC97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f2f70826ca83a37a668f21a309a794a77551a9c","datavalue":{"value":{"entity-type":"item","numeric-id":4978023,"id":"Q4978023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c0923d816c9ede62d938e78143ad8384c1f546b","datavalue":{"value":{"amount":"+0.7879942059516907","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":"Q3177774$410C301A-0121-4878-AAFC-9AAB3AB5090F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4d7a9319b56b714e9ec0725132434db923f01d1","datavalue":{"value":{"entity-type":"item","numeric-id":987844,"id":"Q987844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"390d76826a2a23ca86c155bb357f61ad4ab2f545","datavalue":{"value":{"amount":"+0.7866643667221069","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":"Q3177774$1944E60A-E9B2-450C-ADA5-5259ACE960E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3177774","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3177774"}}}}}