A learning automata based approach to the bounded-diameter minimum spanning tree problem
Javad Akbari Torkestani, Zahra Rezaei · Journal of the Chinese Institute of Engineers · 2012
The bounded diameter minimum spanning tree (BDMST) problem aims at finding the minimum weight spanning tree subject to a predefined diameter constraint. Due to the NP-hardness of the BDMST problem, several heuristic and meta-heuristic approaches have been proposed to find a near optimal solution in a reasonable time. In this article, a distributed algorithm is proposed for solving the BDMST problem based on learning automata. Generally, the proposed algorithm consists of two main phases. In the former phase, the proposed algorithm forms the action-set of learning automata and paths from the root to every other node. The latter phase constructs different spanning trees until it finds the optimum one. To show the performance of the proposed algorithm, it is compared with one of the well-known methods. Experimental results confirm the superiority of the proposed algorithm both in terms of the computational complexity and the weight of the spanning tree.