{"entities":{"Q753848":{"pageid":755697,"ns":120,"title":"Item:Q753848","lastrevid":64079271,"modified":"2026-04-11T17:30:14Z","type":"item","id":"Q753848","labels":{"en":{"language":"en","value":"On the computational complexity of upper fractional domination"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4181398"}},"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":"Q753848$99012415-0D8D-4E53-ABE3-6A778AB7FFBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be86ee108c5dcf0b3b1d18be2f9c8e3e84030f13","datavalue":{"value":{"text":"On the computational complexity of upper fractional domination","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q753848$DD736F1C-0B44-478B-A0F4-B445FFE22223","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"feb3d9d7d1af96d663de5c6ccc0a7ea2edb8e9ec","datavalue":{"value":"0717.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753848$F8A57020-DC84-472A-9924-3E882EA64677","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5f1a56cdc38a4fd52aa6c5be92ed9878318b8424","datavalue":{"value":"10.1016/0166-218X(90)90065-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753848$7D25BCE2-2236-46A7-8B3E-3E9108DC882D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b8e74a5be98cf438dbfeade23eb8229a716f1dd","datavalue":{"value":{"entity-type":"item","numeric-id":753844,"id":"Q753844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$C2A8C184-647F-4E7D-83F5-D8C8BCEE8A23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c9d1c9ba6bd3f4aa96f0d37d0211dfaad48b281","datavalue":{"value":{"entity-type":"item","numeric-id":251500,"id":"Q251500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$AFE321EF-33FF-4652-A2AA-C887EEB82642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"20be73a7a55c4bc82d2a38877aebc7a1d1482e6d","datavalue":{"value":{"entity-type":"item","numeric-id":753846,"id":"Q753846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$729F30CF-3FA0-4FF7-9874-BEFE2DF14D2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8aa89cb72bd02f5111f41a72bd591d4d453547cb","datavalue":{"value":{"entity-type":"item","numeric-id":1223689,"id":"Q1223689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$CE77C06F-D598-4FDF-9217-0B8129C3E5A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$AB866798-1229-41A5-AD2C-F5391246D73E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q753848$9C5CE5DD-E824-417E-8B61-A959B4964885","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"57cc99a9c8bec52d64b8ce4bba8cdab286dca67f","datavalue":{"value":"Two well-studied parameters of graphs are \\(\\gamma\\) (G) and \\(\\Gamma\\) (G), the minimum and maximum cardinality over all minimal dominating sets in G. The authors study a nondiscrete generalization of \\(\\Gamma\\) (G): the maximum weight over all minimal dominating functions \\(\\Gamma_ f(G)\\). They show that (1) \\(\\Gamma_ f(G)\\) is computable and is always a rational number; (2) the decision problems corresponding to the problems of computing \\(\\Gamma\\) (G) and \\(\\Gamma_ f(G)\\) are NP-complete; (3) for trees \\(\\Gamma_ f(G)=\\Gamma (G)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q753848$6CEE3282-71BA-4669-8304-65D119836502","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753848$1EF54232-7462-4650-A6A9-DBA416EE88F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753848$1D706A20-DDB0-434B-B4F7-3587675F1A81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753848$56B59F31-45E8-4D69-BE75-4BA399003D95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"056762cc29f7def5b6fb10ccab906956851594a0","datavalue":{"value":"4181398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753848$315E9CCE-2B65-44CB-AA94-8916684BDB25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q753848$5F77CAEC-1131-40A3-935D-DC50370FE86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"970f22a1cf7be79036759afd1a3f62d34918a36e","datavalue":{"value":"maximum weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q753848$ECC43565-E7BB-48AE-AAAD-E1B2A20D4B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71ad6967f00f1712f6b8f054a464475c86a4d6da","datavalue":{"value":"minimal dominating functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q753848$A3DF2AC0-D5F2-4FFE-ACBB-EED5D25E6DB2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a201a8779f110985d707176577b688d9a6216e1","datavalue":{"value":{"entity-type":"item","numeric-id":649735,"id":"Q649735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$198875B7-B6F4-44A6-9B5C-977C38179128","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":"Q753848$D04F1811-98E8-4E52-88C0-8FA384AF22EB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aef048424f8e40282ec79e433746e5961d6d013b","datavalue":{"value":{"entity-type":"item","numeric-id":1115456,"id":"Q1115456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$E4BC178D-6A88-4912-987B-FEE422E74026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"620a70fca5fb59651dbcadad21647a81ccd1c71d","datavalue":{"value":{"entity-type":"item","numeric-id":3859781,"id":"Q3859781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$40A9E2FF-F4A7-4CC0-9589-3A005FCCC171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917f1b4fbbce5af73cd4b1f0fc4af43e9153d67e","datavalue":{"value":{"entity-type":"item","numeric-id":3820628,"id":"Q3820628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$6355172B-EA5C-46D0-A965-7FFBC2F1A467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd77d1fbc3c3585d04500e3d9743b2f951baf630","datavalue":{"value":{"entity-type":"item","numeric-id":5202214,"id":"Q5202214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$B9E3C274-4373-4A9A-9691-2D65F836DBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03dc55bd228ad5f447b3d39106ed210cc5daa457","datavalue":{"value":{"entity-type":"item","numeric-id":1157348,"id":"Q1157348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$27D71E7B-2CD6-4B81-ADFF-97794CA86EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d92f358c0e2fdfb70e81fff9516d786bb3b08c6b","datavalue":{"value":{"entity-type":"item","numeric-id":5753985,"id":"Q5753985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$F273ABDD-AA02-4F01-B55D-4771301ED259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$AA8DBCE9-498A-47C0-BAAB-513F9F1021EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$AE4439EA-395B-4712-8626-989C252B72D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36ecac86f23f6878965655e2b9b37eea24469d25","datavalue":{"value":{"entity-type":"item","numeric-id":4194994,"id":"Q4194994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$814B50C0-2EEB-4A91-876D-BC6CFEC01D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6129c6604e56f216d051f9a24ed984aeeaadcf5b","datavalue":{"value":{"entity-type":"item","numeric-id":3032297,"id":"Q3032297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$0D31B691-B7E9-4D97-8E17-EDC146B35AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49cd57de3077cedf167c4cfbb473079f46f9dbb7","datavalue":{"value":{"entity-type":"item","numeric-id":1838422,"id":"Q1838422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$01575DE2-838D-4824-A283-98E250775747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"325fbfd9424b214813f2e57a2da9d93d1a3255fb","datavalue":{"value":{"entity-type":"item","numeric-id":4123349,"id":"Q4123349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$E3CE0D67-F2DA-48B7-91D0-124CE55E0E1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16cb3804603e3e741811eb5bd552495dc96aa1b2","datavalue":{"value":{"entity-type":"item","numeric-id":1254104,"id":"Q1254104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$63BAD8C1-63B2-46BC-82A5-2145B3F4F506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3eca1f792744dc0b3f0be36615602475f01c97","datavalue":{"value":{"entity-type":"item","numeric-id":1098861,"id":"Q1098861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$27D8DE0F-2EF2-4C29-A0A7-18C7223CE757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c66319ecf0caff7d798a39de5750d2791e9e6c56","datavalue":{"value":{"entity-type":"item","numeric-id":3822197,"id":"Q3822197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753848$90CFF81C-25D5-4A62-B98C-5E840AFA71CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cfb9f68a7141319098e500df11487ef2ca70e34","datavalue":{"value":{"entity-type":"item","numeric-id":1421481,"id":"Q1421481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b74c399dcbd0c9e12e77c46129834874a3b0ef99","datavalue":{"value":{"amount":"+0.89670330286026","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":"Q753848$07A56FF8-8048-41DF-A677-AFB5811A3B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d4c38e9b2f914553c7d4c204be281fe571079f","datavalue":{"value":{"entity-type":"item","numeric-id":5287870,"id":"Q5287870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a2eb8ee2601d7dec6bb3125b768f6fff503e133","datavalue":{"value":{"amount":"+0.8935349583625793","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":"Q753848$8F6847C5-EA1D-449B-A98A-D4B60CA2FE73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b179a81994010e3bad7489937bd42785ad504e65","datavalue":{"value":{"entity-type":"item","numeric-id":3201105,"id":"Q3201105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5ebc70baa4403989edc9cc3a8eb732ef22441b8","datavalue":{"value":{"amount":"+0.8897198438644409","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":"Q753848$70F044A5-235E-470E-84A2-CC0581D70E35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4b9db04d67f50956871d256f4ee7bd160b3ce8f","datavalue":{"value":{"entity-type":"item","numeric-id":5284022,"id":"Q5284022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"466522df1b2f60b0034fdfb6592b79cae27e70ba","datavalue":{"value":{"amount":"+0.8628135919570923","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":"Q753848$F4FD64B1-21E2-4521-88E3-88F0BDDF398F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee22f56dd65bd0d4853f7f269995a70baf55d304","datavalue":{"value":{"entity-type":"item","numeric-id":4734763,"id":"Q4734763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a09c734a5a220274895ff3a41fa24f8e626abf2","datavalue":{"value":{"amount":"+0.8061406016349792","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":"Q753848$0E4A75E4-B398-4CF9-9BB4-7C25D0ED2D15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of upper fractional domination","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_computational_complexity_of_upper_fractional_domination"}}}}}