Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Pradip K Srimani Articles by Zhenyu Xu

27th International Conference on Distributed Computing Systems Workshops (ICDCSW'07)

Toronto, Canada

June 22-June 29

ISBN: 0-7695-2838-4

	ASCII Text	x
	Pradip K Srimani, Zhenyu Xu, "Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set," Distributed Computing Systems Workshops, International Conference on, pp. 3, 27th International Conference on Distributed Computing Systems Workshops (ICDCSW'07), 2007.

	BibTex	x
	@article{ 10.1109/ICDCSW.2007.73, author = {Pradip K Srimani and Zhenyu Xu}, title = {Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set}, journal ={Distributed Computing Systems Workshops, International Conference on}, volume = {0}, year = {2007}, issn = {1545-0678}, pages = {3}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICDCSW.2007.73}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Distributed Computing Systems Workshops, International Conference on TI - Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set SN - 1545-0678 SP EP A1 - Pradip K Srimani, A1 - Zhenyu Xu, PY - 2007 KW - null VL - 0 JA - Distributed Computing Systems Workshops, International Conference on ER -

Pradip K Srimani, Clemson University,USA

Zhenyu Xu, Clemson University,USA

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDCSW.2007.73

In this paper, we present a self-stabilizing algorithm that computes the breadth first spanning tree in arbitrary graph, with O(n3) time complexity using the unfair central daemon. We then propose a self-stabilizing algorithm to compute the weakly connected minimal dominating set in a graph using the same model and provide its correctness and complexity analysis; as far as we know, this is the first self-stabilizing algorithm to compute such sets.

Citation:

Pradip K Srimani, Zhenyu Xu, "Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set," icdcsw, pp.3, 27th International Conference on Distributed Computing Systems Workshops (ICDCSW'07), 2007

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.