TY - JOUR
ID - 1208
TI - An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs
JO - Algebraic Structures and Their Applications
JA - AS
LA - en
SN - 2382-9761
AU - Rajaati, M.
AU - Hooshmandasl, M.R.
AU - Shakiba, A.
AU - Sharifani, P.
AU - Dinneen, M.J.
AD - Department of Computer Science, Yazd University, Yazd, Iran.
AD - Department of Computer Science,
Vali-e-Asr University of Rafsanjan,
Rafsanjan, Iran.
AD - Department of Computer Science,
Yazd University, Yazd, Iran.
AD - Department of Computer Science,
The University of Auckland,
Auckland, New Zealand.
Y1 - 2018
PY - 2018
VL - 5
IS - 1
SP - 23
EP - 39
KW - Mixed Dominating Set
KW - Generalized Series-Parallel
KW - Parse Tree
KW - Tree-width
DO - 10.22034/as.2018.1208
N2 - 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.
UR - https://as.yazd.ac.ir/article_1208.html
L1 - https://as.yazd.ac.ir/article_1208_a3d01b0ef81b9ace16f3dc16a272884d.pdf
ER -