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
(8)
Approximate Algorithm
Connected Dominating Set
Dominating Set
Fault Tolerant
Generic Algorithm
Heterogeneous Network
Wireless Ad Hoc Network
Wireless Network
Related Publications
(1)
Constructing kConnected mDominating Sets in Wireless Sensor Networks
Subscribe
Academic
Publications
On approximation algorithms of kconnected mdominating sets in disk graphs
On approximation algorithms of kconnected mdominating sets in disk graphs,10.1016/j.tcs.2007.05.025,Theoretical Computer Science,My T. Thai,Ning Zha
Edit
On approximation algorithms of kconnected mdominating sets in disk graphs
(
Citations: 18
)
BibTex

RIS

RefWorks
Download
My T. Thai
,
Ning Zhang
,
Ravi Tiwari
,
Xiaochun Xu
Connected Dominating Set
(CDS) has been proposed as the virtual backbone to alleviate the broadcasting storm in wireless ad hoc networks. Most recent research has extensively focused on the construction of 1Connected 1Dominating Set (1CDS) in homogeneous networks. However, the nodes in the CDS need to carry other node’s traffic and nodes in wireless networks are subject to failure. Therefore, it is desirable to construct a
fault tolerant
CDS. In this paper, we study a general
fault tolerant
CDS problem, called kConnected mDominating Set (kmCDS), in heterogeneous networks. We first present two approximation algorithms for 1mCDS and kkCDS problems. Using disk graphs to model heterogeneous networks, we show that our algorithms have a constant approximation ratio. Based on these two algorithms, we further develop a general algorithm for kmCDS. We also provide an interesting analysis for a special case of kmCDS, where k=m+1.
Journal:
Theoretical Computer Science  TCS
, vol. 385, no. 13, pp. 4959, 2007
DOI:
10.1016/j.tcs.2007.05.025
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
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
Citation Context
(9)
...Later, to enhance fault tolerance of wireless network, multiconnected multidominating set has been studied by many papers such as [6], [7], [10], [
11
], [15], [19], etc...
...Here, Thai, Zhang, Tiwari and Xu [
11
] (2007) studied approximation algorithms of �� connected �� dominating sets in disk graphs, but their �� − �� − ������ is not totally dominating...
...10. endfor 11. let �� �� 0�� 0 be the shortest path in �� 12. �� = �� ∪{all nodes in �� �� 0�� 0 } 13. Compute Block(D) 14. endwhile 15. return �� Lemma 4: At most two new nodes are added into at each augmenting step [
11
]...
Yefang Li
,
et al.
Construction of 1 and 2Connected kTotally Dominating Set in Disk Gra...
...Another approach uses the Maximal Independent Set (MIS) problem to find a minimum number of disjoint nodes that cover all the nodes in the network and then selects gateway nodes to connect them [
5
]‐[8]...
Pedro M. Wightman
,
et al.
An optimal solution to the MCDS problem for topology construction in w...
...For this reason, most research studies in this area focus on reducing the size of a CDS [5], [6], [7], [8], [9], [
10
], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], [24]...
...There exist some works [7], [8], [9], [
10
] that focus on constructing kconnected mdominating sets for fault tolerance...
Donghyun Kim
,
et al.
Constructing Minimum Connected Dominating Sets with Bounded Diameters ...
...The related works to us are [8, 9,10,11,
12
,13]...
...Thai et al. proposed a centralized algorithm [
12
] which requires the input graph to be at least max(k, m) connected...
...Lemma 3.2 [
12
] : In a UDG G, there exists a node that is...
Yongzhao Bian
,
et al.
Construction of a Fault Tolerance Connected Dominating Set in Wireless...
...The most related works to us are [9], [10], [11], [
12
] and [13]...
...In [
12
], a centralized algorithm was proposed which requires the input graph to be at least max(k, m) connected...
Yiwei Wu
,
et al.
Construction algorithms for kconnected mdominating sets in wireless ...
References
(7)
Computers and Intractability: A Guide to the Theory of NPCompleteness
(
Citations: 19196
)
Michael Randolph Garey
,
David S. Johnson
Conference:
Artificial Evolution  AE
, 1979
Unit disk graphs
(
Citations: 579
)
Brent N. Clark
,
Charles J. Colbourn
,
David S. Johnson
Journal:
Discrete Mathematics  DM
, vol. 86, no. 13, pp. 165177, 1990
Connected Dominating Sets in Wireless Networks with Different Transmission Ranges
(
Citations: 45
)
My T. Thai
,
Feng Wang
,
Dan Liu
,
Shiwei Zhu
,
Dingzhu Du
Journal:
IEEE Transactions on Mobile Computing  TMC
, vol. 6, no. 7, pp. 721730, 2007
Approximation Algorithms for Connected Dominating Sets
(
Citations: 532
)
Sudipto Guha
,
Samir Khuller
Conference:
European Symposium on Algorithms  ESA
, pp. 179193, 1996
On greedy construction of connected dominating sets in wireless networks
(
Citations: 46
)
Yingshu Li
,
My T. Thai
,
Feng Wang
,
Chihwei Yi
,
Pengjun Wan
,
Dingzhu Du
Journal:
Wireless Communications and Mobile Computing
, vol. 5, no. 8, pp. 927932, 2005
Sort by:
Citations
(18)
P01471  Undergraduate elective experience in psychiatry  a personal account and literature review
H. RussellReddish
,
P. Temple
,
J. Beezhold
Journal:
European Psychiatry  EUR PSYCHIAT
, vol. 26, pp. 475475, 2011
Construction of 1 and 2Connected kTotally Dominating Set in Disk Graph
Yefang Li
,
Tianping Shuai
,
Wenbao Ai
Conference:
International Joint Conference on Computational Sciences and Optimization  CSO
, 2011
A Mathematical Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks
Pedro Wightman
,
Aldo Fabregas
,
Miguel Labrador
Journal:
IEEE Latin America Transactions  IEEE LAT AM TRANS
, vol. 9, no. 4, pp. 534541, 2011
Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks
(
Citations: 5
)
Rajiv Misra
,
Chittaranjan A. Mandal
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 21, no. 3, pp. 292302, 2010
An optimal solution to the MCDS problem for topology construction in wireless sensor networks
Pedro M. Wightman
,
Aldo Fabregas
,
Miguel A. Labrador
Conference:
IEEE LatinAmerican Conference on Communications  LATINCOM
, 2010