[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Algorithms for Minimum m-Connected k-Dominating Set Problem

  • Conference paper
Combinatorial Optimization and Applications (COCOA 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4616))

  • 1564 Accesses

Abstract

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios.

This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001 and 10531070.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alzoubi, K.M., Wan, P.-J., Frieder, O.: Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks 4(1), 22–29 (2002)

    Google Scholar 

  2. Bredin, J.L., Demaine, E.D., Hajiaghayi, M., Rus, D.: Deploying sensor networks with guaranteed capacity and fault tolerance. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 309–319. ACM Press, New York (2005)

    Chapter  Google Scholar 

  3. Dai, F., Wu, J.: On constructing k-connected k-dominating set in wireless networks. In: IEEE International Parallel and Distributed Processing Symposium, IEEE Computer Society Press, Los Alamitos (2005)

    Google Scholar 

  4. Kuhn, F., Moscibroda, T., Wattenhofer, R.: Fault-Tolerant Clustering in Ad Hoc and Sensor Networks. In: Proceedings 26th International Conference on Distributed Computing Systems (ICDCS) (2006)

    Google Scholar 

  5. Koskinen, H., Karvo, J., Apilo, O.: On improving connectivity of static ad-hoc networks by adding nodes. In: Proceedings of the 4th annual Mediterranean Workshop on Ad Hoc Networks (Med-Hoc-Net), pp. 169–178 (2005)

    Google Scholar 

  6. Li, Y.S., Thai, M.T., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks. Wiley Journal on Wireless Communications and Mobile Computing 5(8), 927–932 (2005)

    Article  Google Scholar 

  7. Shang, W.-P., Yao, F., Wan, P.-J., Hu, X.-D.: Algorithms for minimum m-connected k-tuple dominating set problem. Theoretical Computer Science (submitted)

    Google Scholar 

  8. Sinha, P., Sivakumar, R., Bharghavan, V.: Enhancing ad hoc routing with dynamic virtual infrastructures. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, pp. 1763–1772 (2001)

    Google Scholar 

  9. Tarjan, R.: Depth first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  10. Wan, P.-J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications 9(2), 141–149 (2004)

    Article  Google Scholar 

  11. Wang, F., Thai, T.: On the construction of 2-connected virtual backbone in wireless networks. IEEE Transactions on Wireless Communications (to appear)

    Google Scholar 

  12. Wu, W., Du, H., Jia, X., Li, Y., Huang, C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoretical Computer Science 352(1), 1–7 (2006)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Andreas Dress Yinfeng Xu Binhai Zhu

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shang, W., Yao, F., Wan, P., Hu, X. (2007). Algorithms for Minimum m-Connected k-Dominating Set Problem. In: Dress, A., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2007. Lecture Notes in Computer Science, vol 4616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73556-4_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-73556-4_21

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-73555-7

  • Online ISBN: 978-3-540-73556-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics