{"entities":{"Q1664084":{"pageid":1674825,"ns":120,"title":"Item:Q1664084","lastrevid":43266603,"modified":"2025-07-22T23:33:32Z","type":"item","id":"Q1664084","labels":{"en":{"language":"en","value":"More results on the complexity of domination problems in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6924906"}},"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":"Q1664084$A1A00F8D-AB48-4AF5-9CBB-DC658C609668","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"db25a02588b501bf48efc8eca772f070e6ecfe46","datavalue":{"value":{"text":"More results on the complexity of domination problems in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1664084$3B2BEA2E-1348-4547-A791-DCF841997569","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c264922f91d08871838a4411208d3353706debc3","datavalue":{"value":"1407.68191","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$21D571E4-EC92-44D1-8BAA-62AC2E8BBB76","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"db939331efcef3cd694c9a73c645c02901f938a9","datavalue":{"value":"10.1504/IJICOT.2017.10004701","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$558BCDB2-BE7B-4B22-8686-D790BF3FC52B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a1b7c76d48bb1e0dac160345f59745fc2a059b6","datavalue":{"value":{"entity-type":"item","numeric-id":226963,"id":"Q226963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664084$B0D18AAF-C0CF-40A2-8D9F-F638F38F2C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebf2ec2b74efc27b89370d28fd6d179e59643761","datavalue":{"value":{"entity-type":"item","numeric-id":1199621,"id":"Q1199621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664084$0529CF86-4D20-4BDD-B0FD-3C4E5BEAF11E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3e9e59970b6096537ac135b2cc16d1c02a64695","datavalue":{"value":{"entity-type":"item","numeric-id":274526,"id":"Q274526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1664084$1F6A549E-00B0-47B3-8892-9D07B5554913","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"13cdd6edc13ae30df49ead881dcc6c954c3f5ea5","datavalue":{"value":{"time":"+2018-08-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":"Q1664084$E8B1D054-7395-41F8-A236-B9AF356B0FC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"634508733238284aed945bff37d88e40b8a9bbe7","datavalue":{"value":"Summary: Given a graph \\(G=(V,E)\\) and an integer \\(r\\geq 1\\), we call `\\(r\\)-dominating code' any subset \\(C\\) of \\(V\\) such that every vertex in \\(V\\) is at distance at most \\(r\\) from at least one vertex in \\(C\\). We investigate and locate in the complexity classes of the polynomial hierarchy, several problems linked with domination in graphs, such as, given \\(r\\) and \\(G\\), the existence of, or search for, optimal \\(r\\)-dominating codes in \\(G\\), or optimal \\(r\\)-dominating codes in \\(G\\) containing a subset of vertices \\(X\\subset V\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$E304EF77-5ABB-419A-B5EF-7AD903424D22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$EA152568-4D15-457F-BF4F-0F9207E471CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$2C305579-3AFA-44AE-AED5-E0D33457DC92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$C354C73E-3679-4CA0-9A87-1F776A407D4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c1175c1761b2ce51cedfa2d895458b1d0b02bc3","datavalue":{"value":"6924906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$2EC7632C-C33D-49D1-9FE5-0E5ED150FA55","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$1B4EBE26-CAF0-4C05-9EF5-378DA0C7B984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$BB165B16-E254-4819-9DD6-AF709EBAE951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fae759507bb9563b997a3ae1e2c1987b9dc770fd","datavalue":{"value":"covering radius","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$FE651451-1FF0-42B1-8CFF-C648DB7F057B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c5d90a4764eb642089384ca5d890be80895980d","datavalue":{"value":"dominating codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$C9470172-0E1E-4C1B-B01A-F2AF79C53879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$D24E4585-7F0E-4EA2-ADB8-A9EA73D1B872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4881dceebcfc2cfaaf48b0eeca275f318bc3a7ae","datavalue":{"value":"hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$51BCB0D6-6FFA-4B7F-B23E-93067691FE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$A2D14FB4-58D0-4F82-933C-E402896401DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1664084$D57A176A-C7CB-4FD0-B9BB-E3F262BAB9AE","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":"Q1664084$5B4EF1AD-0E5D-494A-B472-17DEAE21F61A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0e5e37eb70b3c99591a999a7deb65f6bfe48ca0d","datavalue":{"value":"https://doi.org/10.1504/ijicot.2017.10004701","type":"string"},"datatype":"url"},"type":"statement","id":"Q1664084$6A46716D-50E9-4E9C-9C1F-86D2947056BD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"576a62a3d170010abf8bfcd35cff1f3080f1bb5c","datavalue":{"value":"W2607172406","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1664084$977EA900-CE05-44AB-95E0-9D71EAB54B5A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"298b11a541827d9399703eb7ea26e32e59d82090","datavalue":{"value":{"entity-type":"item","numeric-id":5437229,"id":"Q5437229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beb18c97439de4f2b0d5823419b34bf87c1ad04b","datavalue":{"value":{"amount":"+0.92947197","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$181838E8-F6E5-443F-9EF2-7491F9ABE0A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33b5e8628115c2fd2340bee09afcfe1d8d930cc9","datavalue":{"value":{"entity-type":"item","numeric-id":3405168,"id":"Q3405168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cb6ba781ce5b204ffe9eae0d99042c65887c0c4","datavalue":{"value":{"amount":"+0.9290999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$600613BF-AB54-4712-A64E-AC5189BBFA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60a3101b6b9e0a64f02aeb6924cdb5ed08cdf7a8","datavalue":{"value":{"entity-type":"item","numeric-id":2895354,"id":"Q2895354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9feb85e7bf5feece41da41e2c2a3fff049bc75a7","datavalue":{"value":{"amount":"+0.92477655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$CF0338C6-3CB8-42A7-A3AE-28D54743ABC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3cf14f009af5f09846ceef68cb3ff232d75c96c","datavalue":{"value":{"entity-type":"item","numeric-id":3615796,"id":"Q3615796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c2b87e7f961f801b62f25ac37b71636de500810","datavalue":{"value":{"amount":"+0.9214794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$51DCA009-D092-439F-B661-C8D8CE139812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17b150de7f070ad650ae8072149da7f10c43ae3c","datavalue":{"value":{"entity-type":"item","numeric-id":3004664,"id":"Q3004664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"133ac9ee6e35b8c78328a3840d23b3b4d44b792a","datavalue":{"value":{"amount":"+0.91678363","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$7515F151-2FAA-473C-8D6F-CFD9EC39F708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fa3d324ee982fd68bd4801bd02c2a33d9e92eac","datavalue":{"value":{"entity-type":"item","numeric-id":2820195,"id":"Q2820195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a8de95f096262581f3fe5a3007f1bf727e7e290","datavalue":{"value":{"amount":"+0.915585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$B64D0B15-ED4D-4F94-A1BC-58184994DDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d22acd94750aaac44fb2579c1ca314d498592a04","datavalue":{"value":{"entity-type":"item","numeric-id":5002958,"id":"Q5002958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e7e871188b8e61fb20b350c42a5d51255aae3bb","datavalue":{"value":{"amount":"+0.91371775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$43637CBE-EEC6-419B-9FDD-BBD62F03303D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6a10675bf57dfa487683644600d75e13c8c2057","datavalue":{"value":{"entity-type":"item","numeric-id":1209148,"id":"Q1209148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e2fdca7ecb88260b1a7dc71d16be92b695b9916","datavalue":{"value":{"amount":"+0.91207343","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$508D3374-07AE-4A46-82B0-50D030493CAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c68182459facf67e54c21e241f7f6ef6271bfddd","datavalue":{"value":{"entity-type":"item","numeric-id":958210,"id":"Q958210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d54873bd4f1bfe4f0c0460d6c7501cb18b321ae","datavalue":{"value":{"amount":"+0.91178274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$A400D02F-C025-4D3D-9C69-39C5135BB388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c43bfc836abdcb0b56f6d1851bc4e4f4f8760fe4","datavalue":{"value":{"entity-type":"item","numeric-id":5492926,"id":"Q5492926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d54873bd4f1bfe4f0c0460d6c7501cb18b321ae","datavalue":{"value":{"amount":"+0.91178274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1664084$9035E8A9-7F91-4F9D-B755-31DD20F43FBF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1664084","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1664084"}}}}}