{"entities":{"Q1371054":{"pageid":1381794,"ns":120,"title":"Item:Q1371054","lastrevid":68754435,"modified":"2026-04-13T01:50:33Z","type":"item","id":"Q1371054","labels":{"en":{"language":"en","value":"Algorithmic aspects of majority domination"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1080274"}},"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":"Q1371054$3528D717-5299-4C76-8639-A827ABAB5D2B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb2ca4f955a27659174ac582642cd24d3e77a522","datavalue":{"value":{"text":"Algorithmic aspects of majority domination","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1371054$EE088F26-806B-4BF7-959F-AC492E50394D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"94d1e9049e7dc70b00686b90289c2e879221bb6e","datavalue":{"value":"0882.05114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$916004E9-ACBD-400F-B78E-C18C9713B095","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"73c7847d8ff878c68f30cbc65ff523b663a8c4b5","datavalue":{"value":{"entity-type":"item","numeric-id":233434,"id":"Q233434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1371054$E6982D53-6574-41CA-86EC-FA94375719C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1371054$5F362378-6330-4701-9BE8-73E5196D7DB1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fc770cd89d4fae0e8d7b267c7a43d9a33ef28782","datavalue":{"value":{"entity-type":"item","numeric-id":168175,"id":"Q168175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1371054$383C0CB5-F868-42D7-9234-CF1C89BE4BEB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41bd464af959f1d39dcdde9372100cb844fa6305","datavalue":{"value":{"time":"+1998-03-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":"Q1371054$DDDD6D91-24CB-4ABC-B376-249A7AB9D89C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ddb8e2424e3f87b12938c7a1bdf41e57dd5126e","datavalue":{"value":"The majority dominating function of a graph \\(G\\) is a function \\(g: V(G)\\to\\{-1,1\\}\\) such that for at least half of the vertices \\(v\\) of \\(G\\) the sum of values of \\(g\\) over the closed neighbourhood of \\(v\\) is at least 1. The minimum value of the sum of values of \\(g\\) taken over all majority dominating functions of \\(G\\) is the majority domination number of \\(G\\). The paper studies the algorithmic complexity of finding the majority domination number for trees, cographs and \\(k\\)-trees. Cographs are defined in such a way that \\(K_1\\) is a cograph and for cographs \\(G\\) and \\(H\\) also \\(G\\cup H\\) and \\(G\\times H\\) are cographs. (Probably, here the symbols \\(\\cup\\) and \\(\\times\\) denote other operations than disjoint union and Cartesian product, because otherwise cographs would be only graphs without edges.) The \\(k\\)-trees are defined so that \\(K_k\\) is a \\(k\\)-tree and any graph obtained from a \\(k\\)-tree by adding a new vertex and joining it with all vertices of a \\(k\\)-clique is again a \\(k\\)-tree. It is proved that there is an \\(O(n^2)\\)-time algorithm for computing the majority domination number for a tree, an \\(O(n^3)\\)-time algorithm for a cograph and a polynomial-time algorithm for a \\(k\\)-tree, where \\(n\\) is the number of vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$B308B6B1-3C0A-4D7D-A269-40A5393081F9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$AC4734DA-8D16-4815-80CC-D3B13776D24D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$38E0C28E-28C7-489E-9045-C67D1DECF0A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$78EC884A-BF86-4328-B8F7-CBF95F573594","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"370d3f2d022d46ff15a5095b443a5b070d67169e","datavalue":{"value":"1080274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$4869AB02-8045-410E-927D-2BF9F10777C1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d4df72e45a5d1687c54956789b5ed4af765618c","datavalue":{"value":"majority dominating function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$6D0F3D7F-B617-4BE1-987F-66BF27152467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85e23f0fa663977dfbaabb27c2d17a6d134bf0ac","datavalue":{"value":"majority domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$BE68B7A1-EE2E-47E9-BB8A-DDEE9C7A9F22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93077cc6db36e07d535db7c75a2f03eb0743cd04","datavalue":{"value":"algorithmic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$38FF5FDF-9AFF-47C3-9FC7-0806A1BB6176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$19EEF4C7-653A-47CF-9834-B6BACBABC5F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df7fe14c7b38fce52b1c24ba095651ec0120be54","datavalue":{"value":"cographs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$5B70F79D-92D4-4D2B-8BB2-209CA2DB5E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ed4725d47dfe790698b61f83244da63193f579f","datavalue":{"value":"\\(k\\)-trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1371054$0909F669-B7A9-4230-AD03-C58B1A0DB177","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1371054$86DE5D50-0B6B-4F63-95EE-4CDE5FA512A3","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":"Q1371054$A34EEF1A-837A-4D0A-A5DE-C370E3D1C1A1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"26f3ca180f8c78f8829e33363c3103d1df332633","datavalue":{"value":"https://doi.org/10.11650/twjm/1500405694","type":"string"},"datatype":"url"},"type":"statement","id":"Q1371054$F7C8A5CE-6EB0-461C-BD73-B25B5B0374F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c79634f0b9e2230544425b7afc9fd777ae1046b1","datavalue":{"value":"W2123426099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$58497E6C-90D0-47B7-ABE9-0D8F8EDD48CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9580d2f13501f645466034d29fe511618f729c33","datavalue":{"value":"10.11650/TWJM/1500405694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1371054$B9ABC3F9-2CF6-444F-90F6-419EE12E55BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83261446118cddc173e9718074f26a1223074bb7","datavalue":{"value":{"entity-type":"item","numeric-id":3384120,"id":"Q3384120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de2d840723eff9f9e56aee830bc9e275346ef2b3","datavalue":{"value":{"amount":"+0.9033369","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":"Q1371054$1D38A95F-D342-47FF-8E8F-318BB604E6AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"000f504d487f29ca12a686c8561f6e9cc0d111e5","datavalue":{"value":{"entity-type":"item","numeric-id":2851502,"id":"Q2851502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"731c1eeb30a521ea0f3639583eaeabcb5937e944","datavalue":{"value":{"amount":"+0.8916396","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":"Q1371054$310C8847-D13E-4DC2-977B-BA5F0991296D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57df306bb9a782e519ab8e4abb4d955e74625fe7","datavalue":{"value":{"entity-type":"item","numeric-id":1028119,"id":"Q1028119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5433bb703663227cc3cbcc206594d4ad7680c289","datavalue":{"value":{"amount":"+0.8893976","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":"Q1371054$FDF8E916-9984-41D7-8FC5-C12E54FFDF37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89c381e5c80994d66cad5bca5d7bfb45dca3d22d","datavalue":{"value":{"entity-type":"item","numeric-id":5431324,"id":"Q5431324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9f43b2d034b2676ff7d28415393638363ad218a","datavalue":{"value":{"amount":"+0.8877819","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":"Q1371054$BFE58254-7D3E-4AE7-9857-3CCC11DA566C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39ac6cb0c3e8edb558d4c410404ed4abac43a4c8","datavalue":{"value":{"entity-type":"item","numeric-id":3419763,"id":"Q3419763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9f43b2d034b2676ff7d28415393638363ad218a","datavalue":{"value":{"amount":"+0.8877819","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":"Q1371054$D0E42D79-8A8C-4889-9C1E-55FC3B0F377E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0de662d88c427188b7ae27b984a0db4ec0010f00","datavalue":{"value":{"entity-type":"item","numeric-id":4247463,"id":"Q4247463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"547887ee919a3f0dc298431379a3fd44e3a1f07a","datavalue":{"value":{"amount":"+0.88260436","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":"Q1371054$691CA4E4-1405-4FEA-8D36-5D7128BAEA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"287e9347e2c1d54f5e9056289582b4891566327a","datavalue":{"value":{"entity-type":"item","numeric-id":4819698,"id":"Q4819698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaac281c1a5529c2ae6d95e3175ab11dad89d986","datavalue":{"value":{"amount":"+0.8824471","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":"Q1371054$D3E621F6-6D39-4649-97B5-84A1B671D5BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0c89624493849dc316b6cc664a69252613e821b","datavalue":{"value":{"entity-type":"item","numeric-id":2762872,"id":"Q2762872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40809e2f1602029018abad37dff9a27010ae4a36","datavalue":{"value":{"amount":"+0.87948966","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":"Q1371054$9EEC2882-7CE5-4A24-B9CB-68787F106E19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc69529c7ecca3ccab88c238209c2a41bbb1a224","datavalue":{"value":{"entity-type":"item","numeric-id":5946744,"id":"Q5946744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdaa63129468010878313c14b7ee6148d04be53a","datavalue":{"value":{"amount":"+0.87791806","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":"Q1371054$B1A15CCD-FB76-4773-AD3A-CBE7D43BAD69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09cc100c2535b6ddd689b9e52387b8e3e2bcb778","datavalue":{"value":{"entity-type":"item","numeric-id":5369511,"id":"Q5369511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1edc001ebe7adda76d6f3e072c7061bd5b845520","datavalue":{"value":{"amount":"+0.87280107","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":"Q1371054$E0324BB9-D169-48AF-8D61-26BAB6EB2D3C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithmic aspects of majority domination","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithmic_aspects_of_majority_domination"}}}}}