An Efficient Algorithm for Mixed Domination on Generalized Series-Parallel Graphs

Abstract

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.