an efficient algorithm for mixed domination on generalized series-parallel graphs

A mixed dominating set s of a graph g = (v, e) is a subset of vertices and edges like s ⊆ v ∪ e such that each element v ∈ (v ∪ e) s is adjacent or incident to at least one element in s. the mixed domination number γm(g) of a graph g is the minimum cardinality among all mixed dominating sets in g. the problem of finding γ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 γm(g) where g is a generalized series-parallel graph.