- 期刊
- OpenAccess
A Linear-Time Self-Stabilizing Algorithm for the Minimal 2-Dominating Set Problem in General Networks
並列摘要
Kamei and Kakugawa have recently proposed a self-stabilizing algorithm for the minimal k-dominating set problem. Their algorithm is a general form of the maximal-independent-set algorithm proposed by Shukla et al. The results in their paper are for any tree network that assumes Dijkstra's central demon model. In particular, the worst-case stabilization time is claimed to be O(n^2), where n is the number of nodes in the system. In this paper, we generalize their results for the case k=2. We show that their algorithm with k=2, when operating in any general network, is self-stabilizing under the central demon model, and solves the minimal 2-dominating set problem. We also derive that the worst-case stabilization time is linear, i.e., O(n). A bounded function technique is employed in obtaining these results.
被引用紀錄
延伸閱讀
- LIU, X., SHEN, X., & ZHANG, Y. (2001). Absolute Stability of Nonlinear Systems with Time Delays and Applications to Neural Networks. Mathematical Problems in Engineering, 2001(), 413-431. https://doi.org/10.1155/S1024123X01001715
- Yang, X. S. (2008). Existence and Global Exponential Stability of Periodic Solutions for General Neural Networks with Time-Varying Delays. International Journal of Mathematics and Mathematical Sciences, 2008(), 833-846. https://doi.org/10.1155/2008/843695
- Guo, Y. X., & Xue, M. Z. (2009). Periodic Solutions and Exponential Stability of a Class of Neural Networks with Time-Varying Delays. Discrete Dynamics in Nature and Society, 2009(), 620-633. https://doi.org/10.1155/2009/415786
- Mostafa, E. S. M. E. (2014). On the Solution of a Nonlinear Semidefinite Program Arising in Discrete-Time Feedback Control Design. Journal of Applied Mathematics, 2014(), 482-495-645. https://doi.org/10.1155/2014/683797
- Tseng, M. L. (1997). Design of Self-Organizing Probabilistic Neural Networks. 華岡工程學報, (11), 33-47. https://doi.org/10.29987/CCUHKJE.199706.0004