{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:42:02Z","timestamp":1753890122668,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","issue":"Graph Theory","license":[{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T00:00:00Z","timestamp":1532995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>A mixed dominating set for a graph $G = (V,E)$ is a set $S\\subseteq V \\cup E$ such that every element $x \\in (V \\cup E) \\backslash S$ is either adjacent or incident to an element of $S$. The mixed domination number of a graph $G$, denoted by $\\gamma_m(G)$, is the minimum cardinality of mixed dominating sets of $G$. Any mixed dominating set with the cardinality of $\\gamma_m(G)$ is called a minimum mixed dominating set. The mixed domination set (MDS) problem is to find a minimum mixed dominating set for a graph $G$ and is known to be an NP-complete problem. In this paper, we present a novel approach to find all of the mixed dominating sets, called the AMDS problem, of a graph with bounded tree-width $tw$. Our new technique of assigning power values to edges and vertices, and combining with dynamic programming, leads to a fixed-parameter algorithm of time $O(3^{tw^{2}}\\times tw^2 \\times |V|)$. This shows that MDS is fixed-parameter tractable with respect to tree-width. In addition, we theoretically improve the proposed algorithm to solve the MDS problem in $O(6^{tw} \\times |V|)$ time.<\/jats:p><jats:p>Comment: Accepted for the publication in the Journal of Discrete Mathematics &amp;amp;   Theoretical Computer Science (DMTCS). 25 pages, 4 figures, 17 tables, 4   algorithms<\/jats:p>","DOI":"10.23638\/dmtcs-20-2-2","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:40:32Z","timestamp":1743698432000},"source":"Crossref","is-referenced-by-count":0,"title":["On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width"],"prefix":"10.23638","volume":"vol. 20 no. 2","author":[{"given":"M.","family":"Rajaati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. R.","family":"Hooshmandasl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. J.","family":"Dinneen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Shakiba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2018,7,31]]},"container-title":["Discrete Mathematics &amp; Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1612.08234v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1612.08234v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T16:40:32Z","timestamp":1743698432000},"score":1,"resource":{"primary":{"URL":"http:\/\/dmtcs.episciences.org\/2615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,31]]},"references-count":0,"journal-issue":{"issue":"Graph Theory","published-online":{"date-parts":[[2018,7,31]]}},"URL":"https:\/\/doi.org\/10.23638\/dmtcs-20-2-2","relation":{"has-preprint":[{"id-type":"arxiv","id":"1612.08234v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1612.08234v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1612.08234","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1612.08234","asserted-by":"subject"}]},"ISSN":["1365-8050"],"issn-type":[{"type":"electronic","value":"1365-8050"}],"subject":[],"published":{"date-parts":[[2018,7,31]]},"article-number":"2615"}}