On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2
Voir la notice de l'article provenant de la source Episciences
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.
@article{DMTCS_2018_20_2_a0,
author = {Rajaati, M. and Hooshmandasl, M. R. and Dinneen, M. J. and Shakiba, A.},
title = {On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {20},
number = {2},
year = {2018},
doi = {10.23638/DMTCS-20-2-2},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-2/}
}
TY - JOUR AU - Rajaati, M. AU - Hooshmandasl, M. R. AU - Dinneen, M. J. AU - Shakiba, A. TI - On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width JO - Discrete mathematics & theoretical computer science PY - 2018 VL - 20 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-2/ DO - 10.23638/DMTCS-20-2-2 LA - en ID - DMTCS_2018_20_2_a0 ER -
%0 Journal Article %A Rajaati, M. %A Hooshmandasl, M. R. %A Dinneen, M. J. %A Shakiba, A. %T On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width %J Discrete mathematics & theoretical computer science %D 2018 %V 20 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-2/ %R 10.23638/DMTCS-20-2-2 %G en %F DMTCS_2018_20_2_a0
Rajaati, M.; Hooshmandasl, M. R.; Dinneen, M. J.; Shakiba, A. On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 2. doi: 10.23638/DMTCS-20-2-2
Cité par Sources :