{"entities":{"Q1108792":{"pageid":1119541,"ns":120,"title":"Item:Q1108792","lastrevid":66734901,"modified":"2026-04-12T12:30:58Z","type":"item","id":"Q1108792","labels":{"en":{"language":"en","value":"Parallel circle-cover algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068278"}},"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":"Q1108792$2283DB27-6662-4A1E-BAAA-5F5BD72C59B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d5398288007139bb4d772e1623aebf87546706e","datavalue":{"value":{"text":"Parallel circle-cover algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108792$9E97122C-F919-487E-9A7B-57BE519BD950","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4e52e3db0a8f959b12d32a2d087b0cffc166ace","datavalue":{"value":"0654.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108792$208A465F-2570-49D7-80D5-3A1E167C1AB0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7c9614bc2b712cac741c541d83def5ded6ea014","datavalue":{"value":"10.1016/0020-0190(88)90068-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108792$9228C28B-A82D-438F-9D2B-985E4D40D6F4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f04044f52fa6e66fcf9bb794751a3ff14954e256","datavalue":{"value":{"entity-type":"item","numeric-id":218028,"id":"Q218028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$C7770FBC-51F5-4BFB-B1EC-808794DB7023","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":"Q1108792$01E370DF-CDFA-4FA4-B8BE-BE7A2616ABD7","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":"Q1108792$CC6EBAC2-1FCD-453A-AF3E-1E95BBC953DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e93a111275e926c8e2ec62f087ccd7894c936dd4","datavalue":{"value":"Given a set of n circular-arcs, each possibly having a real weight, we consider the problem of finding a subset of the arcs whose union covers the whole circle. We provide parallel algorithms running in O(log n) and \\(O(\\log^ 2 n)\\) time, respectively, for finding a circle-cover with the smallest number of arcs and with the smallest overall weight. The algorithms require, respectively, \\(O(n^ 2/\\log n+qn)\\) and \\(O(n^ 3/\\log n)\\) processors on a shared memory model (SMM) of parallel computers, where q-1 is the minimum number of arcs crossing any point of the circle.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108792$E4C3E3EC-E034-4E8B-80F9-47DA601C4EFC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108792$B9599352-E6AD-4D8D-87ED-CE3F966E94FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4e1df7ba929664ba7b91d5a816f05411516abc3","datavalue":{"value":"52C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108792$BC4FEBE0-E8FC-4B85-8D25-2F8F47974322","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0b281259726895b38ecf2a387aba4e6ed97f931","datavalue":{"value":"4068278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108792$2CFB2B47-FCE7-4998-8DB5-64CA722F020B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0095e9a48b164f928fcc6500a04324bc3ef40dc6","datavalue":{"value":"circle-cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108792$0AFF7965-3C12-4C83-A4E4-1ED2BE5FBB66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108792$8F2ACB45-D8D4-4445-A4A6-98F07408E353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db5e0888fa9957c443e210eb3c88f717e276ae13","datavalue":{"value":"parallel processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108792$3C55C2CB-281F-4CD8-B766-C6821A6C7E80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108792$FA169685-475C-4511-9899-D0BED125A197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a02f46aae6cbe0b6a4524588f9410b3b1d3162ec","datavalue":{"value":"SMM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108792$3D913C01-ACBE-4542-BBCD-455849116731","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":"Q1108792$F328FC1B-6691-44CC-ACF1-6F7866089CA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"524b0498335c2c58fe2497e5bd718c4aed1afc0f","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90068-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108792$7A017AD8-CEA9-4DB5-B7A7-4C080A6530C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42203e9a6a6af13d93900d7a98c903edf754a29a","datavalue":{"value":"W1965213248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108792$1A75FDCE-7ED2-4B81-ADF9-58346FB1723B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9348e1c9ad5465f71daa6350b7dddd13e3961e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1098312,"id":"Q1098312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$12080D74-ADCC-43E8-9383-5583CB43772E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6f2fa62f920fb46fbd79ba851e5cbf1f877777","datavalue":{"value":{"entity-type":"item","numeric-id":3922163,"id":"Q3922163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$3497F75E-C928-4FF3-AE93-5C753107CF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee0db509cdfbb391996bd24af57ade555fd0c93c","datavalue":{"value":{"entity-type":"item","numeric-id":3659131,"id":"Q3659131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$2C7BCAF7-6D03-4C2F-98EC-EAD73F5BDB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a8b9e919631fd13058b126b3a76e6cf944e4f8e","datavalue":{"value":{"entity-type":"item","numeric-id":1073571,"id":"Q1073571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$79FAE9F7-020C-438E-A450-3633D3BDC672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af19f40a86b1a81b10c5d2b02c9dee04a257de7f","datavalue":{"value":{"entity-type":"item","numeric-id":1076605,"id":"Q1076605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$04A40F4A-E036-42E4-AAA9-4374EEA49316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb4098fbc07af19a3657d7d25d62392729a3cf1","datavalue":{"value":{"entity-type":"item","numeric-id":790622,"id":"Q790622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$C144172B-32B0-4394-8846-717D95B52F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d37fc9515499cef0e7d4a680a5c07d2a0db5e8e9","datavalue":{"value":{"entity-type":"item","numeric-id":4101728,"id":"Q4101728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$A974CB7C-0D99-4D68-B6A5-FF5FBE1C3159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51826f25d95525fd11a7363d44c95522afa1732","datavalue":{"value":{"entity-type":"item","numeric-id":3683547,"id":"Q3683547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108792$4F6476C4-AC64-4D49-B89D-D5530D94F950","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe8e982c5652dda5f3b58aa66a40b8b9d6862649","datavalue":{"value":{"entity-type":"item","numeric-id":1823694,"id":"Q1823694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ae6b1d781a12be672fffc23c08d855fbc8b5dbd","datavalue":{"value":{"amount":"+0.9435351490974426","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":"Q1108792$6567ED28-C459-4486-BE0C-7867484BED28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee5a36b53229abeee632689d39cd10a86ed7ae96","datavalue":{"value":{"entity-type":"item","numeric-id":1823682,"id":"Q1823682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c38a1dd696952d34f955c2a3b7fde3515715bf01","datavalue":{"value":{"amount":"+0.9288960695266724","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":"Q1108792$BAE4E568-AD41-4F25-AED2-0D55D5EECECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9201e3e1ae1bc606edf433416d211cf59a295d46","datavalue":{"value":{"entity-type":"item","numeric-id":1123605,"id":"Q1123605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7a76e6d95c4002bae20e4b62a488475dddc747d","datavalue":{"value":{"amount":"+0.9125321507453918","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":"Q1108792$CB212B7B-C35C-4D7B-B926-17C12D209853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57e094ce784df1fd2cd65946bd4b424d237fc718","datavalue":{"value":{"entity-type":"item","numeric-id":5917729,"id":"Q5917729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31efe28b3b3c1b4d7f624318f88f40963bf4db8d","datavalue":{"value":{"amount":"+0.8702644109725952","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":"Q1108792$8350FE42-6D50-4686-B21E-629D77E9B3C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04a6442582194e7d99f45393de0529156b830c64","datavalue":{"value":{"entity-type":"item","numeric-id":790622,"id":"Q790622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc4c0ff23a54b5a6559cae01c7081879ae18dc04","datavalue":{"value":{"amount":"+0.8537311553955078","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":"Q1108792$7944C72B-0DDF-4BAC-AFCA-6999E6BAC4EB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel circle-cover algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_circle-cover_algorithms"}}}}}