On Constructing 2-Connected2-Dominating Set Using Distributed Algorithm

Xue Yu Wang

doi:10.4028/www.scientific.net/AMR.850-851.588

Paper Titles

Adaptive Sliding Mode Observer for Back-EMF in Direct Torque Control of Brushless DC Motor
p.572

Physiological Signal Detection Instrument Based on FPGA
p.576

The Website Interface Design and Investigation of Interactive Availability
p.580

Zig Bee-Based Wireless Sensor Network Design of Irrigation Systems
p.584

On Constructing 2-Connected2-Dominating Set Using Distributed Algorithm
p.588

Information Mining Based on Multi-Granularity News Fusion
p.592

Application of Network Technology in Campus Public Address System
p.596

Research and Design on Inspection Robot for High-Voltage Transmission Lines
p.600

Comparative Study of 428XL and GEIST438 Telemetry Seismis Instrument
p.604

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 850-851On Constructing 2-Connected2-Dominating Set Using...

On Constructing 2-Connected2-Dominating Set Using Distributed Algorithm

Abstract:

This paper proposes a distributed algorithm to construct a 2-connected 2-dominating set. The main ingredient of this algorithm is that the nodes in the loop are 2-vertex connected. It starts from any node, and forms a localized loop made by dominating nodes. The nodes in the loop are 2-vertex connected. Basing on this loop, the algorithm continue to construct other loops formed by dominating nodes until the nodes out loops are 2-dominated.

You might also be interested in these eBooks

Advances in Applied Sciences and Manufacturing

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 850-851)

Pages:

588-591

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.850-851.588

Citation:

Cite this paper

Online since:

December 2013

Authors:

Xue Yu Wang*

Keywords:

Connected Dominating Set, Distributed Algorithm, Wireless Sensor Network (WSN)

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory of NP-Completeness. Freeman, San Francisco(1978).

Google Scholar

[2] S. Guha, S. Khuller. Approximation Algorithms for Connected Dominating Sets. Algorithmica, 1998, 20(4): pp.374-387.

DOI: 10.1007/pl00009201

Google Scholar

[3] J. Wu , H. Li. On Calculating Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks. Proc. Third Int'l Workshop on Discrete Algorithms and Methods for Mobile Computing and Comm., 1999, pp.7-14.

DOI: 10.1145/313239.313261

Google Scholar

[4] Bo Han, HaoHuan Fu, Lidong Lin and Weijia Jia . Efficient Construction of Connected Dominating Set in Wireless Ad Hoc Networks[C]. 2004 IEEE International Conference on Mobile Ad-hoc and Sensor Systems: pp.570-572.

DOI: 10.1109/mahss.2004.1392211

Google Scholar

[5] Zhang Jing, Jia Chun-Fu. Minimum Connected Dominating Set Algorithm with Weight in Wireless Sensor Networks[C] The 4th International Conference on Wireless Communications, Networking and Mobile Computing 2008 1-4.

DOI: 10.1109/wicom.2008.953

Google Scholar