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

2017/08/01 by Rajaati, M., Sharifani, P., Shakiba, A. +2
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1708.00240

Abstract

A mixed dominating set S of a graph G=(V,E) is a subset 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 know to be NP-complete. In this paper, we present an explicit polynomial-time algorithm to construct a mixed dominating set of size γ_m(G) by a parse tree when G is a generalized series-parallel graph.

Related

• On Mixed Domination in Generalized Petersen Graphs
• A Linear Algorithm for Computing γ_[1,2]-set in Generalized Series-Parallel Graphs
• Total mixed domination in graphs
• Upper and Lower Bounds on Approximating Weighted Mixed Domination
• Some Algorithmic Results on Restrained Domination in Graphs