On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Rajaati, M en
dc.contributor.author Hooshmandasl, MR en
dc.contributor.author Dinneen, Michael en
dc.contributor.author Shakiba, A en
dc.date.accessioned 2019-03-20T03:56:45Z en
dc.date.issued 2018-07 en
dc.identifier.citation Discrete Mathematics & Theoretical Computer Science 20(2) Article number 2 2018 en
dc.identifier.issn 1462-7264 en
dc.identifier.uri http://hdl.handle.net/2292/46169 en
dc.description.abstract A mixed dominating set for a graph G=(V,E) is a set S⊆V∪E such that every element x∈(V∪E)∖S is either adjacent or incident to an element of S. The mixed domination number of a graph G, denoted by γm(G), is the minimum cardinality of mixed dominating sets of G. Any mixed dominating set with the cardinality of γ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(3tw2×tw2×|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(6tw×|V|) time. en
dc.publisher Discrete Mathematics & Theoretical Computer Science en
dc.relation.ispartofseries Discrete Mathematics & Theoretical Computer Science en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.rights.uri http://creativecommons.org/licenses/by/4.0/ en
dc.title On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width en
dc.type Journal Article en
dc.identifier.doi 10.23638/DMTCS-20-2-2 en
pubs.issue 2 en
pubs.volume 20 en
dc.rights.holder Copyright: The authors en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en
pubs.subtype Article en
pubs.elements-id 753530 en
dc.relation.isnodouble 699946 *
pubs.org-id Science en
pubs.org-id School of Computer Science en
pubs.record-created-at-source-date 2018-12-26 en

Full text options

Find Full text

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by/4.0/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by/4.0/


Search ResearchSpace

Advanced Search