CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
HYBRID ANN AND FIREWORKS ALGORITHM FOR REAL-TIME SOFTWARE RELIABILITY PREDICTION

Ivy Botchway Felix Larbi Aryeh Boniface Kayode Alese
Random Articles
Reseach Article

Minimum Matching Dominating Sets and its Applications in Wireless Networks

by C.D.Guruprakash, Dr. B.P.Mallikarjunaswamy
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 30 - Number 3
Year of Publication: 2011
Authors: C.D.Guruprakash, Dr. B.P.Mallikarjunaswamy
10.5120/3623-5059

C.D.Guruprakash, Dr. B.P.Mallikarjunaswamy . Minimum Matching Dominating Sets and its Applications in Wireless Networks. International Journal of Computer Applications. 30, 3 ( September 2011), 23-27. DOI=10.5120/3623-5059

@article{ 10.5120/3623-5059,
author = { C.D.Guruprakash, Dr. B.P.Mallikarjunaswamy },
title = { Minimum Matching Dominating Sets and its Applications in Wireless Networks },
journal = { International Journal of Computer Applications },
issue_date = { September 2011 },
volume = { 30 },
number = { 3 },
month = { September },
year = { 2011 },
issn = { 0975-8887 },
pages = { 23-27 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume30/number3/3623-5059/ },
doi = { 10.5120/3623-5059 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:15:58.019548+05:30
%A C.D.Guruprakash
%A Dr. B.P.Mallikarjunaswamy
%T Minimum Matching Dominating Sets and its Applications in Wireless Networks
%J International Journal of Computer Applications
%@ 0975-8887
%V 30
%N 3
%P 23-27
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

For wireless ad hoc network no fixed infrastructure or centralized management, a Minimum Matching Dominating Set (MMDS) has been proposed as the virtual backbone. The MMDS of a graph representing a network has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which each node has the same transmission range. However, in practice, the transmission ranges of all nodes are not necessary equal. In this paper, we model a network as a disk graph and introduce the MMDS problem in disk graphs. We present three constant approximations algorithms to obtain a minimum MMDS of a given network. These algorithms can be implemented as distributed algorithms. Furthermore, we show the size relationship between a maximal independent set and a MMDS as well as the bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.

References
  1. T. Thai Feng Wang Dan Liu Shiwei Zhu Ding-Zhu Du “Connected Dominating Sets in Wireless Networks with Different Transmission Ranges”Dept. of Computer Science & Enginering University of Minnesota Minneapolis, MN 55455.
  2. Minimum connected dominating sets and maximal independent sets in unit disk graphs, Weili Wu et al
  3. Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links, Ding-Zhu Du et al.
  4. B. Clack, C. Colbourn, and D. Johnson, ”Unit Disk Graphs,”Discrete Mathematics, vol. 86, pp. 165–177, 1990.
  5. P.-J. Wan, K. M. Alzoubi, and O. Frieder, ”Distributed Construction on Connected Dominating Set in Wireless Ad Hoc Networks”,Proceedings of the Conference of the IEEE Communications Society (INFOCOM), 2002.
  6. Y. Li, M. T. Thai, F. Wang, C.-W. Yi, P.-J. Wang, and D.-Z.Du, ”On Greedy Construction of Connected Dominating Sets in Wireless Networks”, Special issue of Wireless Communications and Mobile Computing (WCMC), 2005.
  7. S. Funke, A. Kesselman, U. Meyer, and M. Segal,”A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs”, 1st IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), 2005.
  8. M. Cardei, M.X. Cheng, X. Cheng, and D.-Z. Du, ”Connected Domination in Ad Hoc Wireless Networks”, Proceedings of the Sixth International Conference on Computer Science and Informatics (CSI), 2002.
  9. S. Guha and S. Khuller, ”Approximation Algorithms for Connected Dominating Sets”, Algorithmica, vol. 20, pp. 374– 387,1998.
  10. L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, and L.-I. Ko, ”A Greedy Approximation for Minimum Connected Dominating Sets”, Theoretical Computer Science, 2005.
  11. J. Wu and H. Li, ”On Calculating Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks”, Proceedings of the Third International Workshop Discrete Algorithms and Methods for Mobile Computing and Comm., 1999.
  12. Y. Li, S. Zhu, M. T. Thai, and D.-Z. Du, ”Localized Construction of Connected Dominating Set in Wireless Networks”, NSF International Workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks, 2004.
  13. T.W.Haynes and P.J.Slater “Paired Domination in Graphs Networks,32(1998),199-206.
  14. T.W.Haynes and P.J.Slater “Paired Domination and paired dominating number,2091995),65-72.
  15. K.M. Alzoubi, P.-J. Wang, and O. Frieder, ”Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks”, Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2002.
  16. B. Das, R. Sivakumar, and V. Bharghavan, ”Routing in Ad Hoc Networks Using a Spine”, International Conference on Computers and Communication Networks, 1997.
  17. B. Das and V. Bharghavan, ”Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets”, International Conference on Communications, 1997.
  18. R. Sivakumar, B. Das, and V. Bharghavan, ”An Improved Spinebased Infrastructure for Routing in Ad Hoc Networks”, IEEE Symposium on Computers and Communications, 1998.
  19. M. R. Garey, D. S. Johnson, ”Computers and Intractability. A guide to the Theory of NP-completeness”, Freeman, New York, 1979.
  20. K.M. Alzoubi, P.-J. Wan, and O. Frieder, ”New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks”, Proceedings of the 35th Hawaii International Conference on System Scicences, Hawaii, 2002.
  21. K.M. Alzoubi, P.-J. Wan, and O. Frieder, ”Distributed Heuristics for Connected Dominating Sets in Wireless Ad Hoc Networks”, Journal of Communications and Networks, vol. 4, no. 1, March 2002.
  22. H. Breu and D.G. Kirkpatrick. Unit disk graph recognition is NP-hard. Computational Geometry. Theory and Applications, 9(1-2):3–24, 1998.
  23. T.M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178–189, 2003.
  24. X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks, 42:202–208,2003.
  25. B. N. Clark, C. J. Colburn, and D. S. Johnson. Unit disks graphs. Discrete Mathematics,86:165–177, 1990.
  26. I.Cidon and O. Mokryn, ”Propagation and Leader Election in Multihop Broadcast Environment”, The 12th International Sysposium on distributed Computing (DISC), 1998. I.J. Dejter and O. Serra, \E_cient dominating sets in Cayley graphs”, Discrete Applied Mathematics, Vol.129, (2003), pp.319-328.
  27. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, (2000).
  28. Jia Huang and Jun-Ming Xu, \The bondage numbers and efficient dominations of vertex-transitive graphs", Discrete Mathematics, Vol.308,(2008), pp.571-582.
  29. S. Lakshmivarahan and S.K. Dhall, \Ring, torus and hypercube architectures/ algorithms for parallel computing", Parallel Computing, Vol.25,(1999), pp.1877-1906.
  30. J. Lee, \Independent perfect domination sets in Cayley graphs", Journal of Graph Theory, Vol.37, No.4, (2001), pp.213-219.
  31. N. Obradovi_c, J. Peters and Goran Ru_zi_c, \E_cient domination in circulant graphs with two chord lengths", Information Processing Letters,Vol.102, (2007), pp.253-258.
  32. T. Tamizh Chelvam and I. Rani, \Dominating sets in Cayley Graphs on Zn", Tamkang Journal of Mathematics, Vol.38, No.4, (2007), pp.341-345.
  33. T. Tamizh Chelvam and I. Rani, \Independent domination number of Cayley graphs on Zn", The Journal of Combinatorial Mathematics and Combinatorial Computing, Vol.69, (2009), pp.251-255.
Index Terms

Computer Science
Information Sciences

Keywords

Connected Dominating Set Independent Set Minimum Matching dominating sets Unit Disk Graph Wireless Network Virtual Backbone

Powered by PhDFocusTM