On the mixed domination problem in graphs
Journal
Theoretical Computer Science
Journal Volume
476
Pages
84-93
Date Issued
2013
Author(s)
Abstract
A mixed dominating set of a simple graph G=(V,E) is a subset D ⊆ V ∪ E such that every vertex or edge not in D is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to determine a minimum mixed dominating set of G. This paper studies mixed domination in graphs from an algorithmic point of view. In particular, a linear-time labeling algorithm for the mixed domination problem in cacti is presented. In addition, we fix an incomplete proof of the NP-completeness of the mixed domination problem in split graphs Zhao et al. (2011) [23]. Finally,weestablish a primal-dual algorithm for the mixed domination problem in trees.
SDGs
Type
journal article