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 |