{"entities":{"Q2197403":{"pageid":2208146,"ns":120,"title":"Item:Q2197403","lastrevid":53810045,"modified":"2026-01-25T18:23:42Z","type":"item","id":"Q2197403","labels":{"en":{"language":"en","value":"Partitioning vertices into in- and out-dominating sets in digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7242073"}},"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":"Q2197403$6E741CEC-9B8C-4336-8AE4-7FCF2BAC4430","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e46d4a69a2e010fdedfdfcd45a68c901b89f7f12","datavalue":{"value":{"text":"Partitioning vertices into in- and out-dominating sets in digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2197403$29DD342F-F19E-475D-8269-7875640CFF0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd88ef2dc9f0394755df94324a780711bf701c45","datavalue":{"value":"1451.05193","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$4657417F-7D3E-4DBC-AE2B-40E8CC5C0F50","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"25cda160630b5c1ba3cd9eadc9a344d8049e37e8","datavalue":{"value":{"entity-type":"item","numeric-id":2197402,"id":"Q2197402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$37052E7E-B807-4606-9737-81A0C5EAB6DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"18c4b5786397f41ce0b1eb7768d838964033848a","datavalue":{"value":{"entity-type":"item","numeric-id":845826,"id":"Q845826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$5700C446-DE1C-44E1-AD89-D6B0B777456F","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":"Q2197403$12D2A733-E27F-44C2-B7C9-4490F66E64F6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2a92243b7f71031e288e3329b3f00a17d48f45e0","datavalue":{"value":{"time":"+2020-08-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2197403$F16EC6ED-2F86-4B81-966A-75212ABC53C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d382c3baca52ee08597ad50af594bdcce7a09ab5","datavalue":{"value":"Let \\(D\\) be a digraph with the vertex set \\(V(D)\\) and the arc set \\(A(D)\\). A set \\(X\\subseteq V(D)\\) is an out-dominating set if every vertex not in \\(X\\) is adjacent from a vertex in \\(X\\). Similarly, a set \\(X\\subseteq V(D)\\) is an in-dominating set if every vertex not in \\(X\\) is adjacent to a vertex in \\(X\\). Directed \\(p\\)-in \\(q\\)-out domatic partition is the problem that given a digraph \\(D\\) and positive integers \\(p\\) and \\(q\\), determines whether there exists a partition of the vertex set \\(V(D)=I_1\\cup\\cdots\\cup I_p\\cup O_1\\cup\\cdots\\cup O_q\\) such that \\(I_i\\) are in-dominating sets of \\(D\\) for \\(1\\leq i\\leq p\\) and \\(O_j\\) are out-dominating sets of \\(D\\) for \\(1\\leq j\\leq q\\). The IOP problem is the problem that given a digraph \\(D\\), determines whether there exists a partition of the vertex set \\(V(D)=I\\cup O\\) such that \\(I\\) is an in-dominating set and \\(O\\) is an out-dominating sets of \\(D\\). In this article, the authors posed the problem of directed \\(p\\)-in \\(q\\)-out domatic partition, which is a domatic partition problem for digraphs, and investigated the problem whether a given digraph has a partition of the vertices into in- and out-dominating sets. The authors derived the following results: (1) the IOP problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a linear-time algorithm for deciding the existence of such partition. In fact, it would be interesting to discuss the directed \\(p\\)-in \\(q\\)-out domatic partition for various kinds of digraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$230767D2-5F46-4E26-8E79-4955A036AF31","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$C56B25F0-1EA5-4299-820B-D2F36605E3D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$6F4B84B5-C602-4A89-B43A-882EC69472AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$C79B9FF7-4C6D-4793-8F0F-4E3A25053381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$D2EAEB72-0474-4CB4-AF88-2B99A849B105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$5DAA5191-7C2E-4981-A979-736B16A77299","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"43d9cc4265743c4be482aded8e46bd6ffb0f3983","datavalue":{"value":"7242073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$2E66F8AB-63FF-42C0-8DC4-C9261DE22804","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$B9083FA0-D7AA-42BA-B8D3-7DC103EECDFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$65E7963A-6C82-4F6B-AD63-89009AD90DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$9E46F021-6416-4B0E-9C9D-FB788A48416A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1400f673c8dff9a7e3b5a2c22f9e9599511005f","datavalue":{"value":"in-domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$CF485E27-823D-4337-95CF-D8C55C33CB1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f34e7bff759f34edddc4814bd1edd9f1aa5aea4a","datavalue":{"value":"out-domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$B642C00F-F2CF-4FFB-9D8B-4A148FAA33B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"336bd74af33cb6d712e8c8c4ef9e1265f5a77dc7","datavalue":{"value":"domatic partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2197403$34CB9F12-C651-416B-8C7D-77833E8A8B81","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"999fe16790e0a94f054fbae70eaba34b3e52a6fb","datavalue":{"value":{"entity-type":"item","numeric-id":1753363,"id":"Q1753363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$70A9C03A-7BD9-4B90-AFFA-A5098FBC97F2","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":"Q2197403$FAE60B8F-01A8-4FEE-A63A-7FED866CEB1E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"61c91cfbd64826ea94da48bacaa99a5a29bd6c0e","datavalue":{"value":"https://doi.org/10.1016/j.dam.2020.05.021","type":"string"},"datatype":"url"},"type":"statement","id":"Q2197403$804C2CFF-8FAB-4662-8A7B-4EB7EBFFD96D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2b9e085304cfc050c9273c5301147e45cedfce05","datavalue":{"value":"W3035676160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$E46A081B-9651-4FE4-A33F-96AA034441A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b87b5a61636d906acd731555c2b0f8f47e79f206","datavalue":{"value":{"entity-type":"item","numeric-id":998382,"id":"Q998382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$917CCA98-2086-425F-8DEA-C952D567F411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b605b4ecb5c74c1d7cb57b071e20330aabed54ad","datavalue":{"value":{"entity-type":"item","numeric-id":1045016,"id":"Q1045016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$BBF41177-FA6A-4308-B85A-DA16C3849B3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$CDBF0278-8201-4F46-9859-664533659115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72505ced85f775300524892bdc5828b2de2211cd","datavalue":{"value":{"entity-type":"item","numeric-id":4247463,"id":"Q4247463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$572CFE12-4323-4809-AD6A-E4F924655A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7187b9811f8357e780ff72b9b1a0ae6cc20c8484","datavalue":{"value":{"entity-type":"item","numeric-id":5463344,"id":"Q5463344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$01EB4311-1AF7-422C-B627-273434403730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d884434cb8d5f997f1f00ad1b41efed0a0f1e53","datavalue":{"value":{"entity-type":"item","numeric-id":1292825,"id":"Q1292825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$9774A470-6EE6-41D1-B513-52B030D75DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f1abb00be5f39872fb67b2178893201776ea8c6","datavalue":{"value":{"entity-type":"item","numeric-id":3065457,"id":"Q3065457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$2063616D-DBCD-4822-A1D0-50306F9AA73F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56aa07beffcf5cd4668ceb40b044197d8e5f8b9","datavalue":{"value":{"entity-type":"item","numeric-id":4163261,"id":"Q4163261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$D5A0E7B0-AA52-4AC4-9F75-2EA93AD15CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"571289e7c516224687771a058d92473901f168e0","datavalue":{"value":{"entity-type":"item","numeric-id":1168729,"id":"Q1168729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$F40C6E0A-5492-40D0-A7A9-FC79F83D1622","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":"Q2197403$1BB4976D-D85E-4B34-AE79-50968E11DC16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57c096a928efb50d5a3ff2a81ad03eab10f2725f","datavalue":{"value":{"entity-type":"item","numeric-id":4378637,"id":"Q4378637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$0632F9FD-B505-4B98-A77B-3D37D9F7D850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f57b56e4f87ecb4a20fe03987ffda81fe6f0394f","datavalue":{"value":{"entity-type":"item","numeric-id":2485283,"id":"Q2485283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$CB1DD870-1DB9-4A02-B9A4-ABFBF473BE0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e2ea2152030d530210ab36fa86cd121e5617554","datavalue":{"value":{"entity-type":"item","numeric-id":444453,"id":"Q444453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$F0E9E42C-84EC-412D-B0A9-CF65DDAB765A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"785e7851fac401f47fc66697d0bfc439f0b289a0","datavalue":{"value":{"entity-type":"item","numeric-id":4368729,"id":"Q4368729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$D8FC66DA-EBC6-4E34-BA55-9FDEAC0BE14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$1B500DF0-C52C-4700-B346-CE10561EE418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f88392e2d96e6b20b42940bf56c1735eaf4e5420","datavalue":{"value":{"entity-type":"item","numeric-id":3291034,"id":"Q3291034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2197403$EEAB38DE-6E9D-4D05-A2B1-895F16212CA0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"253179b87c8e3fc8a6faa3d3f5c7184d78b79d78","datavalue":{"value":"10.1016/J.DAM.2020.05.021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2197403$CE477319-8652-4D7B-9B54-8788AD010EB3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bcf4592d2378eea9b580407f1aa2b41d3628fc2","datavalue":{"value":{"entity-type":"item","numeric-id":3463017,"id":"Q3463017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7548a876eb3f9f9da8ce5f39e0c114ffb014407c","datavalue":{"value":{"amount":"+0.7680197358131409","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":"Q2197403$F122E661-BE06-4127-A31F-14066B393024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8378edf8ad11485fbcd4e86a12f2e8f02cfd20de","datavalue":{"value":{"entity-type":"item","numeric-id":1292825,"id":"Q1292825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf89d183e6f12d118b5d6fbb11a44562ba1cd722","datavalue":{"value":{"amount":"+0.7616057991981506","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":"Q2197403$8B88D292-AE1F-4333-A609-469F8561D77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a1ac5ba65f26474681cc40f584bf0fe0218ee1c","datavalue":{"value":{"entity-type":"item","numeric-id":3384119,"id":"Q3384119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73e45b087546664ea73b8f448518bc669c58c29e","datavalue":{"value":{"amount":"+0.7610282301902771","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":"Q2197403$8838B61A-FD75-41D3-93E4-E84857803CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66c881eca9d9c16d3a93b8898084d3dad69b82c0","datavalue":{"value":{"entity-type":"item","numeric-id":1704574,"id":"Q1704574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbe9a50366ee795e030a6780ab1228eb8c9ade14","datavalue":{"value":{"amount":"+0.7532645463943481","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":"Q2197403$F1DCB56C-0589-4CA0-8E50-E921B75DA373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"384443d9b692f07a7052029ffe0d7537011328dd","datavalue":{"value":{"entity-type":"item","numeric-id":2629228,"id":"Q2629228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c14152eddd4bc3f061b01071e99ed1ae6b2c2ae","datavalue":{"value":{"amount":"+0.7486780881881714","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":"Q2197403$5D62F252-3B02-4F20-9DDB-80752D5A083C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2197403","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2197403"}}}}}