Finding minimum weight connected dominating set in stochastic graph based on learning automata

详细信息    查看全文

• 作者：Javad Akbari Torkestani^a ; ^{j-akbari@iau-arak.ac.ir} ; Mohammad Reza Meybodi^b
• 关键词：Dominating set ; Minimum connected dominating set ; Stochastic graph ; Learning automata
• 刊名：Information Sciences
• 出版年：2012
• 出版时间：1 October, 2012
• 年：2012
• 卷：200
• 期：Complete
• 页码：57-77
• 全文大小：1714 K

文摘

Finding the minimum weight connected dominating set (MCDS) in an arbitrary graph is an NP-hard problem and several heuristics and approximation methods have been proposed to solve it. Forwarding the messages along the virtual backbone induced by the connected dominating set (CDS) significantly reduces the routing overhead as well as the power consumption by reducing the routing nodes to the backbone nodes. This paper first defines the stochastic MCDS problem where the probability distribution function (PDF) of the random weight associated with the graph vertices is unknown. Then, it presents several learning automata-based algorithms (Algorithms 1-6) to solve the stochastic MCDS problem. Taking advantage of learning automata, the proposed algorithms significantly reduce the number of samples that must be taken from the graph to construct the MCDS. It is proved that by the proper choice of the learning rate, the probability of finding the MCDS is close enough to unity. The standard sampling method (SSM) is the baseline with which we compare the performance of the proposed algorithms. Experimental results show that Algorithm 6 significantly outperforms the SSM and the other proposed algorithms in terms of the sampling rate.