{"entities":{"Q659693":{"pageid":661542,"ns":120,"title":"Item:Q659693","lastrevid":57112215,"modified":"2026-03-26T16:23:36Z","type":"item","id":"Q659693","labels":{"en":{"language":"en","value":"Minimum clique partition in unit disk graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5999833"}},"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":"Q659693$55885CC9-6AA9-43C2-B27D-ACC5FD0EDD03","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e13c02156110141dcf1433ad87a188f0cf2251df","datavalue":{"value":{"text":"Minimum clique partition in unit disk graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q659693$9E54DC73-115A-4451-B276-5ED031010DAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6802ad2b17d4d85063647eac190516f5381ac295","datavalue":{"value":"1244.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$5C52ADCE-1060-4403-9515-6E4A5BE82A9A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5b905a1f97eedf9f0c58cb4ee92d3415099d061","datavalue":{"value":{"entity-type":"item","numeric-id":202655,"id":"Q202655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$E271D58F-7C15-4BE7-BA49-50D43C7DC0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b81a4dc49f2cef20908ab5b4ec5273f96d074360","datavalue":{"value":{"entity-type":"item","numeric-id":188717,"id":"Q188717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$27A19B04-B032-4DFE-9D73-6AA10EC40A84","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$BE3A071D-F788-45B4-82C1-0D6CAC825B55","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a8ae18c3aa8afb0a38e8de58d984f857c905ff39","datavalue":{"value":{"time":"+2012-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q659693$2CC0FD56-D8C3-4171-A1C6-8963411E70E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ffa035b2ae601ba42c62ffbc966cb66e4c7590c","datavalue":{"value":"https://arxiv.org/abs/0909.1552","type":"string"},"datatype":"url"},"type":"statement","id":"Q659693$09643232-3AA1-4A45-B0B2-2F5517C31FE1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e657f2875b20c2dd4939b925117d002f0218eb6","datavalue":{"value":"The minimum clique partition is known to be an NP-hard problem. The paper presents two algorithms for finding approximate solutions of the clique partition of unit disk graphs. A unit disk graph corresponds to a set of points in the plane. Two vertices are adjacent if and only if the distance between corresponding points is at most \\(1\\).  The first algorithm presented in the article is a polynomial approximation scheme that computes an \\((1+\\varepsilon)\\)-approximation in \\(n^{O(1/\\varepsilon^2)}\\) time. The second algorithm is a randomized version with approximation ratio \\(2.16\\) and \\(O(n^2)\\) running time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q659693$7A194913-D33E-4700-9B65-ECF3995E7A9B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$4562ACB7-EBC7-4788-A5FC-0C34E414FD89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$74FC9308-0BA7-4684-A63C-E6FFBC8E27AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$7F678C3C-8C21-493F-B141-9B12BBC4F520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$29BC3061-740C-43B5-844D-1D4253ABF580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$E8B318CD-B917-4736-AD59-45E3C2ACC9F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05fadc7ae381f35d37836a3677fc6e489e32467f","datavalue":{"value":"5999833","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$786B74A4-5814-4943-BB21-50DA237611CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d05f6036e6fa6ac0e370528ac36af787bba46d8e","datavalue":{"value":"clique partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q659693$824D784B-451E-46EA-BC6E-43917AA60D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfa4ce6cfbd5e618995529bd1343a4a7f34072a4","datavalue":{"value":"unit disk graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q659693$31D54E36-805B-42B9-83C2-C1DAFC7E664F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q659693$E8DC8E6F-BA0F-4EDE-9550-D126117BE8B5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$C2B589F6-18D5-4373-B43A-4680CDCFB605","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":"Q659693$42DB313F-A6D5-492E-9535-7B4186C0CA96","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d12af206f51e4cdd18fe5712f7ce7c3a991577b","datavalue":{"value":"W1964336531","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$6F2AB2F1-9120-4C31-80C2-7C4777840D25","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf9b7f8410173a668574fe4a975d25ea3fb9ff59","datavalue":{"value":{"entity-type":"item","numeric-id":3595415,"id":"Q3595415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$5BA92902-C8EC-43B8-A38A-F62F9CD0CC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4a381dce4100bafc346fa18a9f4f26641825a6e","datavalue":{"value":{"entity-type":"item","numeric-id":1384186,"id":"Q1384186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$3CCC64B6-AACE-44B8-B017-F94A7FF6E0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78500d6fcce07550315e59f9dcf0c342a2c4678","datavalue":{"value":{"entity-type":"item","numeric-id":3361924,"id":"Q3361924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$8C882577-E6E9-448E-9D5A-FD2A47EAC565","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da98d83333a4041ba9356afb37323237aa80e4fd","datavalue":{"value":{"entity-type":"item","numeric-id":3259120,"id":"Q3259120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$AF7A4810-6517-4885-A816-962FE26899B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c139cecb5b14a2255ec6337e7f451a94814fd74","datavalue":{"value":{"entity-type":"item","numeric-id":5708492,"id":"Q5708492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$35675706-64D2-437E-93A5-ABDA4C9FC4F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$E56E1305-B6EE-483B-9F5B-45C99FF6B17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87ae4bdd3650dcd3bee3253821f00a83b249f519","datavalue":{"value":{"entity-type":"item","numeric-id":659693,"id":"Q659693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$797994D6-FC38-43BD-9910-64FFC658A3BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faf457f1212ea0750678c0a874399d7e5b07f4bf","datavalue":{"value":{"entity-type":"item","numeric-id":912393,"id":"Q912393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$6DCDF422-5FA6-4416-AC96-A9AEF7D24E79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef661ca1e7c9bc6bc55d8fd79bea07fbc5a6faaa","datavalue":{"value":{"entity-type":"item","numeric-id":2768362,"id":"Q2768362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$90280D02-C14C-4806-BB82-283FCDCF7710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22319ad6f990e9dffb0d33ba4bd0574dbf1b5b3b","datavalue":{"value":{"entity-type":"item","numeric-id":3579437,"id":"Q3579437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$02E17A20-89D5-43A0-98A1-EDE4225D6A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b100803b7aeae0783a4b7b1622bf6ccefa3568aa","datavalue":{"value":{"entity-type":"item","numeric-id":5795745,"id":"Q5795745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$C3B34F8F-BF85-43F4-9CEC-0D68FD4D489C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$49218BC8-9E53-4549-8E8F-ED5B363ACE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a5a23b8465d0f43fc014342b9b71168d1015efb","datavalue":{"value":{"entity-type":"item","numeric-id":1209311,"id":"Q1209311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$D6BC243E-E4E0-4F90-B20C-D0B27B8494D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e28d865b6a527d6aef184a58e15bb15ad21dc2c","datavalue":{"value":{"entity-type":"item","numeric-id":3856819,"id":"Q3856819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$D51BC309-27C2-45EF-BAF9-FC6BC6BA88CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b6a8719e8aff9e5f33e80307f3cbf135664b970","datavalue":{"value":{"entity-type":"item","numeric-id":5336876,"id":"Q5336876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$98895C95-1FB7-4FA7-A528-317F1DF5043E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"408dd9c519dca26be20bfaf9ac6f97bf8229dc64","datavalue":{"value":{"entity-type":"item","numeric-id":4698229,"id":"Q4698229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$23580015-6D30-4329-99EF-AF729651BAF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ba3bd74ef41e0757015be3b53bca7ad9cb71ba","datavalue":{"value":{"entity-type":"item","numeric-id":5463630,"id":"Q5463630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$BD6AE8A4-66A3-47F2-9D75-B99188E6CF23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f8814c2ab77dd2a81c4d16aa171675369d0fdd4","datavalue":{"value":{"entity-type":"item","numeric-id":4962754,"id":"Q4962754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$ECBC5F17-44EE-4739-94C6-98D1BF50CA64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"038f3d090d8afa98521ee1fa0e87fa73a91610d8","datavalue":{"value":{"entity-type":"item","numeric-id":2428685,"id":"Q2428685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$3E8D5C3E-66A6-45FC-9333-68F2B03F967E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"043a4f5f6ca2d93228407a90e0ce6d0443323f45","datavalue":{"value":{"entity-type":"item","numeric-id":3569890,"id":"Q3569890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$B77AC2F6-B266-4C9F-90FB-297519059596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b34a246508428ac62689a0f6e17e01f841a8d923","datavalue":{"value":{"entity-type":"item","numeric-id":3002782,"id":"Q3002782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q659693$F798ECA6-7BD1-426A-B4CF-D6FC41B68B14","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5b91ea3c56783084a662e23056758016b387103c","datavalue":{"value":"10.1007/S00373-011-1026-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q659693$8BCD5E6E-1B39-425C-8A15-4BFD0991A753","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11c023daecd61e8144d3cda62c33500f9260071d","datavalue":{"value":{"entity-type":"item","numeric-id":3569890,"id":"Q3569890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1837bf75c93b4041599eaf045e5ba73ef3025063","datavalue":{"value":{"amount":"+0.8787396550178528","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":"Q659693$CC5678F7-B5E5-4CD3-B1BF-A3659BE7755B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d87459ac6ae4dd0aa42208af5baa9445dbd54864","datavalue":{"value":{"entity-type":"item","numeric-id":2428685,"id":"Q2428685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f3362052aa25d64131be81ccaa6f4c918429abc","datavalue":{"value":{"amount":"+0.8706601858139038","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":"Q659693$84A5D9BE-A79D-4083-91F0-8991EB83273F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b759b203d583d7af0115ce4fc4001b5f245bc583","datavalue":{"value":{"entity-type":"item","numeric-id":3095042,"id":"Q3095042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c9e3da4549130742a6617af89246d6a77d5734d","datavalue":{"value":{"amount":"+0.8200733661651611","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":"Q659693$A0C6482F-AB7F-4538-99F8-8B4A52D30D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b2c34f0320b1ab8391abafa1bba2a4c2ee067bc","datavalue":{"value":{"entity-type":"item","numeric-id":2181244,"id":"Q2181244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2228f9a2f3d80f417cc4993bbe0213aa3f021103","datavalue":{"value":{"amount":"+0.801750123500824","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":"Q659693$2F8E502E-9CD0-4FE5-98F3-B719021B6FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a753cb1a13d74518a87207a1a82ed0c3543ed0cb","datavalue":{"value":{"entity-type":"item","numeric-id":2636809,"id":"Q2636809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"516f4d04d1e5a46b323586a2b38972b4e4c6e3ae","datavalue":{"value":{"amount":"+0.7945653200149536","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":"Q659693$A70CEBA5-BFB2-4919-9F63-C5923389D084","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:659693","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:659693"}}}}}