%0 Journal Article
%T An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs
%J Algebraic Structures and Their Applications
%I Yazd University
%Z 2382-9761
%A Rajaati, M.
%A Hooshmandasl, M.R.
%A Shakiba, A.
%A Sharifani, P.
%A Dinneen, M.J.
%D 2018
%\ 02/01/2018
%V 5
%N 1
%P 23-39
%! An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs
%K Mixed Dominating Set
%K Generalized Series-Parallel
%K Parse Tree
%K Tree-width
%R 10.22034/as.2018.1208
%X A mixed dominating set $S$ of a graph $G=(V, E)$ is a subset of vertices and edges like $S \subseteq V \cup E$ such that each element $v\in (V \cup E) \setminus S$ is adjacent or incident to at least one element in $S$. The mixed domination number $\gamma_m(G)$ of a graph $G$ is the minimum cardinality among all mixed dominating sets in $G$. The problem of finding $\gamma_{m}(G)$ is known to be NP-complete. In this paper, we present an explicit polynomial-time algorithm using the parse tree to construct a mixed dominating set of size $\gamma_{m}(G)$ where $G$ is a generalized series-parallel graph.
%U https://as.yazd.ac.ir/article_1208_a3d01b0ef81b9ace16f3dc16a272884d.pdf