Stochastic Bounded Diameter Minimum Spanning Tree Problem

Article type: Research Article

Authors: Akbari Torkestani, Javad^{a; *}

Affiliations: [a] Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran. j-akbari@iau-arak.ac.ir

Note: [*] Address for correspondence: Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran.

Abstract: In this paper, a learning automata-based algorithm is proposed for approximating a near optimal solution to the bounded diameter minimum spanning tree (BDMST) problem in stochastic graphs. A stochastic graph is a graph in which the weight associated with each edge is a random variable. Stochastic BDMST problem seeks for finding the BDMST in a stochastic graph. To the best of our knowledge, no work has been done on solving the stochastic BDMST problem, where the weight associated with the graph edge is random variable. In this study, we assume that the probability distribution of the edges random weight is unknown a priori. This makes the stochastic BDMST problem incredibly hard-to-solve. To show the efficiency of the proposed algorithm, its results are compared with those of the standard sampling method (SSM). Numerical results show the superiority of the proposed sampling algorithm over the SSM both in terms of the sampling rate and convergence rate.

Keywords: Bounded diameter minimum spanning tree problem, stochastic graph, learning automata, sampling

DOI: 10.3233/FI-2015-1250

Journal: Fundamenta Informaticae, vol. 140, no. 2, pp. 205-219, 2015