Geodesic
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. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-2-2/

Cité par Sources :