@article {
author = {Rajaati, M. and Hooshmandasl, M.R. and Shakiba, A. and Sharifani, P. and Dinneen, M.J.},
title = {An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs},
journal = {Algebraic Structures and Their Applications},
volume = {5},
number = {1},
pages = {23-39},
year = {2018},
publisher = {Yazd University},
issn = {2382-9761},
eissn = {2423-3447},
doi = {10.22034/as.2018.1208},
abstract = {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.},
keywords = {Mixed Dominating Set,Generalized Series-Parallel,Parse Tree,Tree-width},
url = {https://as.yazd.ac.ir/article_1208.html},
eprint = {https://as.yazd.ac.ir/article_1208_a3d01b0ef81b9ace16f3dc16a272884d.pdf}
}