Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Chordal Graph
Connected Graph
Dominating Set
Graph Algorithm
Linear Time
Polynomial Time Algorithm
Subscribe
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
Edit
The algorithmic complexity of mixed domination in graphs
BibTex

RIS

RefWorks
Download
Yancai Zhao
,
Liying Kang
,
Moo Young Sohn
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 polynomialtime algorithm for this problem in trees. Further we design another lineartime labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NPcomplete even when restricted to split graphs, a subclass of chordal graphs.
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 22, pp. 23872392, 2011
DOI:
10.1016/j.tcs.2011.01.029
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.
(
www.sciencedirect.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
References
(22)
Total matchings and total coverings of graphs
(
Citations: 7
)
Y. Alavi
,
M. Behzad
,
L. M. LesniakFoster
,
E. A. Nordhaus
Journal:
Journal of Graph Theory  JGT
, vol. 1, no. 2, pp. 135140, 1977
On total covers of graphs
(
Citations: 4
)
Yousef Alavi
,
Jiuqiang Liu
,
Jianfang Wang
,
Zhongfu Zhang
Journal:
Discrete Mathematics  DM
, vol. 100, no. 13, pp. 229233, 1992
Dominating Sets for Split and Bipartite Graphs
(
Citations: 27
)
Alan A. Bertossi
Journal:
Information Processing Letters  IPL
, vol. 19, no. 1, pp. 3740, 1984
Dominating Sets in Chordal Graphs
(
Citations: 43
)
Kellogg S. Booth
,
J. Howard Johnson
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 11, no. 1, pp. 191199, 1982
The $k$Domination and $k$Stability Problems on SunFree Chordal Graphs
(
Citations: 62
)
Gerard J. Chang
,
George L. Nemhauser
Journal:
Siam Journal on Algebraic and Discrete Methods
, vol. 5, no. 3, 1984