Author/Authors :
RAJAATI, M Department of Computer Science - Yazd University, Yazd, Iran , HOOSHMANDASL, M. R Department of Computer Science - Yazd University, Yazd, Iran , SHAKIBA, A Department of Computer Science Vali-e-Asr - University of Rafsanjan Rafsanjan, Iran , SHARIFANI, P Department of Computer Science - Yazd University, Yazd, Iran , DINNEEN, M. J Department of Computer Science - The University of Auckland Auckland, New Zealand
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 2 (V [ E) n 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.
Keywords :
Mixed Dominating Set , Generalized Series-Parallel , Parse Tree , Tree-width
