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 \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.

کلیدواژه ها:

Mixed Dominating Set ، Generalized Series-Parallel ، Parse Tree ، Tree-width