An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs
نویسندگان
1 Department of Computer Science, Yazd University, Yazd, Iran.
2 Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran.
3 Department of Computer Science, Yazd University, Yazd, Iran.
4 Department of Computer Science, Yazd University, Yazd, Iran.
5 Department of Computer Science, The University of Auckland, Auckland, New Zealand.
doi
10.22034/as.2018.1208چکیده
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.
