Academic
Publications
The algorithmic complexity of mixed domination in graphs

The algorithmic complexity of mixed domination in graphs,10.1016/j.tcs.2011.01.029,Theoretical Computer Science,Yancai Zhao,Liying Kang,Moo Young Sohn

The algorithmic complexity of mixed domination in graphs  
BibTex | RIS | RefWorks Download
Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)∖W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.
Journal: Theoretical Computer Science - TCS , vol. 412, no. 22, pp. 2387-2392, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.