Narrow Results

Min-degree constrained minimum spanning tree (md-MST) problem is an NP-hard combinatorial optimization problem seeking for the minimum weight spanning tree in which the vertices are either of degree one (leaf) or at least degree d ≥ 2. md-MST problem is new to the literature and very few studies have been conducted on this problem in deterministic graph. md-MST problem has several appealing real-world applications. Though in realistic applications the graph conditions and parameters are stochastic and vary with time, to the best of our knowledge no work has been done on solving md-MST problem in stochastic graph. This paper proposes a decentralized learning automata-based algorithm for finding a near optimal solution to the md-MST problem in stochastic graph. In this work, it is assumed that the weight associated with the graph edge is random variable with a priori unknown probability distribution. This assumption makes the md-MST problem incredibly harder to solve. The proposed algorithm exploits an intelligent sampling technique avoiding the unnecessary samples by focusing on the edges of the min-degree spanning tree with the minimum expected weight. On the basis of the Martingale theorem, the convergence of the proposed algorithm to the optimal solution is theoretically proven. Extensive simulation experiments are performed on the stochastic graph instances to show the performance of the proposed algorithm. The obtained results are compared with those of the standard sampling method in terms of the sampling rate and solution optimality. Simulation experiments show that the proposed method outperforms the standard sampling method.

In this paper, we first introduce a network of learning automata, which we call it as distributed learning automata and then propose some iterative algorithms for solving stochastic shortest path problem. These algorithms use distributed learning automata to find a policy that determines a path from a source node to a destination node with minimal expected cost (length). In these algorithms, at each stage distributed learning automata determines which edges to be sampled. This sampling method may result in decreasing unnecessary samples and hence decreasing the running time of algorithms. It is shown that the shortest path is found with a probability as close as to unity by proper choice of the parameters of the proposed algorithms.

A weakly connected dominating set (WCDS) of graph G is a subset of G so that the vertex set of the given subset and all vertices with at least one endpoint in the subset induce a connected sub-graph of G. The minimum WCDS (MWCDS) problem is known to be NP-hard, and several approximation algorithms have been proposed for solving MWCDS in deterministic graphs. However, to the best of our knowledge no work has been done on finding the WCDS in stochastic graphs. In this paper, a definition of the MWCDS problem in a stochastic graph is first presented and then several learning automata-based algorithms are proposed for solving the stochastic MWCDS problem where the probability distribution function of the weight associated with the graph vertices is unknown. The proposed algorithms significantly reduce the number of samples needs to be taken from the vertices of the stochastic graph. It is shown that by a proper choice of the parameters of the proposed algorithms, the probability of finding the MWCDS is as close to unity as possible. Experimental results show the major superiority of the proposed algorithms over the standard sampling method in terms of the sampling rate.