{"entities":{"Q4680214":{"pageid":6709795,"ns":120,"title":"Item:Q4680214","lastrevid":109559468,"modified":"2026-11-13T01:02:32Z","type":"item","id":"Q4680214","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2172821"}},"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":"Q4680214$08B4A3A2-D444-4D92-875C-EDFF3055A912","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d9a7b9bbf27053688f6a39dcfc8e6d2925f2589","datavalue":{"value":"1104.68537","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4680214$C2A15B0B-18C9-4B9B-8B9D-D254E5911C5F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"660e514a90abb1ec460c195c4edfb794fbf73bb0","datavalue":{"value":{"entity-type":"item","numeric-id":4680213,"id":"Q4680213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4680214$F2DCCDF9-E4C5-4125-BDEE-CE0BE4E96334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"562fd1ac726e6d7b200e56d2ebb49ca5c2702596","datavalue":{"value":{"entity-type":"item","numeric-id":214617,"id":"Q214617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4680214$75F1E341-1E5B-41F4-87C1-C836FF9F66EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0825556a1e0b5416c9b3f9c3833e6c4e2d6fcdb0","datavalue":{"value":{"entity-type":"item","numeric-id":6538825,"id":"Q6538825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4680214$172B810D-C880-4AAB-960F-1E09C5D695A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a3a48ccbcb78a0136ad4e7581de5467c9ead0f3","datavalue":{"value":{"entity-type":"item","numeric-id":6897157,"id":"Q6897157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4680214$974F8EFE-691C-4BF7-AB70-2EE8A926C951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"40a3ef7df813e942e338a042aabd077c560c1a0a","datavalue":{"value":{"entity-type":"item","numeric-id":6042939,"id":"Q6042939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4680214$27F46312-D3FB-449D-BD53-E1F89CBB8985","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a2a00d07f06d0a6eedbd13f5ff98a15190e2168e","datavalue":{"value":{"time":"+2006-06-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":"Q4680214$1795D0EE-C1AD-44AD-AB2F-C3FA0EC88B15","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4680214$EAB8DE68-149B-44A1-817D-7AFED94D3BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4680214$04797326-2B4D-4E51-89DF-53A90F899D49","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9f5104e444a2956ec2b85656e92ad275dd38d95","datavalue":{"value":"2172821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4680214$BAF63F3E-4655-424C-BEEF-772078FC0321","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q4680214$D56D4119-51D3-4557-A886-15CD535B86FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4680214$29666603-AD09-4981-948E-0C686DDFACE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q4680214$8958581D-FA0E-4264-BD5E-96732B99B346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f6baa8a009965f4fd44a061128b66ac82033975","datavalue":{"value":"non-approximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4680214$7FE6E3BA-144D-4497-906C-0779AD0A6B30","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":"Q4680214$CDB66C68-E579-49AE-AB92-4BC2C7C29F6E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa3a3d61919ec2ca9c97adedebcedce94cd9f0e8","datavalue":{"value":{"entity-type":"item","numeric-id":5464578,"id":"Q5464578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"513d7b434923cbfaec55a44ef5ec264cd59a2c47","datavalue":{"value":{"amount":"+0.91834295","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":"Q4680214$25581057-BED3-4176-BE05-45AD25187DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aad66cf3725cf6423b96c4939c2fada6a02718a4","datavalue":{"value":{"entity-type":"item","numeric-id":975529,"id":"Q975529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24389eb705704459058c8c0890b25b0239e3645d","datavalue":{"value":{"amount":"+0.916641","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":"Q4680214$F1A134ED-3906-482F-9F4A-F01FE694C979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f2959a72d12e003cee81070e0194b7d48156a6f","datavalue":{"value":{"entity-type":"item","numeric-id":5230381,"id":"Q5230381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"447698f6a4415b99a8b06909c7bd5f48cb4daf86","datavalue":{"value":{"amount":"+0.90585136","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":"Q4680214$EF4FA113-7931-4405-AA47-6789D2C6A7B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60b6b4114a349116bf89c0d3bc9a5fd30639d6bf","datavalue":{"value":{"entity-type":"item","numeric-id":5215462,"id":"Q5215462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"447698f6a4415b99a8b06909c7bd5f48cb4daf86","datavalue":{"value":{"amount":"+0.90585136","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":"Q4680214$B5D8671D-D55B-43CB-9E7A-A94277E7B230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32057594912643b6df5308a19fe19d8b2d7d124e","datavalue":{"value":{"entity-type":"item","numeric-id":1386346,"id":"Q1386346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"681ca52e49dd40718fe1f63c31c03e8cd45dc441","datavalue":{"value":{"amount":"+0.9003809","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":"Q4680214$EE5CB39C-4523-4547-AC2C-237D8E45A01B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ccf84ca6f5283c9f693f56da26e7dd0cbc0e455","datavalue":{"value":{"entity-type":"item","numeric-id":4595486,"id":"Q4595486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"681ca52e49dd40718fe1f63c31c03e8cd45dc441","datavalue":{"value":{"amount":"+0.9003809","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":"Q4680214$020A14F7-D2B6-4724-B994-723CAFF76E69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3e943cc1efc8766e5de3ea583d425c477aba22b","datavalue":{"value":{"entity-type":"item","numeric-id":3634205,"id":"Q3634205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbca373626dd433b87c12c58429dca9aba177da3","datavalue":{"value":{"amount":"+0.8984461","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":"Q4680214$9E535E55-7255-44B9-9E22-3E8F06B2E546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66efa05ab24cb58ac72cb32c3eb16325dbc91321","datavalue":{"value":{"entity-type":"item","numeric-id":958303,"id":"Q958303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"599d673eadb54656367348392fed6c703e46820f","datavalue":{"value":{"amount":"+0.89554894","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":"Q4680214$3DE79102-A5B9-4D3E-BDB5-0C887E8B563A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a32cd0bf6428ca1a3cd889416cf0f85a2b094dfc","datavalue":{"value":{"entity-type":"item","numeric-id":5874545,"id":"Q5874545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6bd8478b75dddc78408ca7154466a11f25eeb32","datavalue":{"value":{"amount":"+0.8922676","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":"Q4680214$8EEB65B1-45BB-41F9-AAFF-8D4CCE601E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7412c5270223927dde477f71ff7e3f0c3d9f588f","datavalue":{"value":{"entity-type":"item","numeric-id":2144267,"id":"Q2144267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6bd8478b75dddc78408ca7154466a11f25eeb32","datavalue":{"value":{"amount":"+0.8922676","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":"Q4680214$F8B444B0-53CF-4F7F-963E-7FB83C9AA3BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"24cd984209b71306b39465da61ddc22c515b24f3","datavalue":{"value":"For a graph \\(G=(E, V)\\), \\(| V| =n\\), and a positive function \\(f(n)\\) the measured dominating set problem is to find the minimum set of vertices \\(D\\), s.t. for any vertex \\(u\\in V- D\\) there exists \\(v \\in D\\) with distance \\((u,v) \\leq f(n)\\). If \\(f(n)=1\\), we get the standard dominating set problem. The Contribution of the paper is the following: A) The problem is NP-hard for \\(f(n)=n^{\\varepsilon },\\, 0<\\varepsilon <1\\). This extends a former result of \\textit{G. J. Chang} and \\textit{G. L. Nemhauser} [Oper. Res. Lett. 1, 214--218 (1982; Zbl 0498.90023)] for \\(f(n)=O(1)\\). B) The problem is approximable with a ratio of \\(O(\\log n)\\) and the log function is the best possible. The same results are proved for the weighted version of the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4680214$57705D3D-3D68-4FC7-A2EF-1E1564958A99","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4680214","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4680214"}}}}}