Abstract
During the last decades, a host of efficient algorithms have been developed for solving the minimum spanning tree problem in deterministic graphs, where the weight associated with the graph edges is assumed to be fixed. Though it is clear that the edge weight varies with time in realistic applications and such an assumption is wrong, finding the minimum spanning tree of a stochastic graph has not received the attention it merits. This is due to the fact that the minimum spanning tree problem becomes incredibly hard to solve when the edge weight is assumed to be a random variable. This becomes more difficult if we assume that the probability distribution function of the edge weight is unknown. In this paper, we propose a learning automata-based heuristic algorithm to solve the minimum spanning tree problem in stochastic graphs wherein the probability distribution function of the edge weight is unknown. The proposed algorithm taking advantage of learning automata determines the edges that must be sampled at each stage. As the presented algorithm proceeds, the sampling process is concentrated on the edges that constitute the spanning tree with the minimum expected weight. The proposed learning automata-based sampling method decreases the number of samples that need to be taken from the graph by reducing the rate of unnecessary samples. Experimental results show the superiority of the proposed algorithm over the well-known existing methods both in terms of the number of samples and the running time of algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chiang TC, Liu CH, Huang YM (2007) A near-optimal multicast scheme for mobile ad hoc networks using a hybrid genetic algorithm. Expert Syst Appl 33:734–742
Rodolakis G, Laouiti A, Jacquet P, Naimi AM (2008) Multicast overlay spanning trees in ad hoc networks: capacity bounds protocol design and performance evaluation. Comput Commun 31:1400–1412
Boruvka O (1926) Ojistém problému minimálním (About a certain minimal problem). Praca Moravske Prirodovedecke Spolecnosti 3:37–58
Kruskal JB (1956) On the shortest spanning sub tree of a Graph and the traveling salesman problem. In: Proceedings of the American mathematical society 7(1):748–750
Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36:1389–1401
Ishii H, Shiode S, Nishida T, Namasuya Y (1981) Stochastic spanning tree problem. Discrete Appl Math 3:263–273
Ishii H, Nishida T (1983) Stochastic bottleneck spanning tree problem. Networks 13:443–449
Mohd IB (1994) Interval elimination method for stochastic spanning tree problem. Appl Math Comput 66:325–341
Ishii H, Matsutomi T (1995) Confidence regional method of stochastic spanning tree problem. Math Comput Model 22(19–12):77–82
Alexopoulos C, Jacobson JA (2000) State space partition algorithms for stochastic systems with applications to minimum spanning trees. Networks 35(2):118–138
Katagiri H, Mermri EB, Sakawa M, Kato K (2004) A study on fuzzy random minimum spanning tree problems through possibilistic programming and the expectation optimization model. In: Proceedings of the 47th IEEE international midwest symposium on circuits and systems
Almeida TA, Yamakami A, Takahashi MT (2005) An evolutionary approach to solve minimum spanning tree problem with fuzzy parameters. In: Proceedings of the international conference on computational intelligence for modelling, control and automation
Hutson KR, Shier DR (2006) Minimum spanning trees in networks with varying edge weights. Ann Oper Res 146:3–18
Fangguo H, Huan Q (2008) A model and algorithm for minimum spanning tree problems in uncertain networks. In: Proceedings of the 3rd international conference on innovative computing information and control (ICICIC’08)
Dhamdhere K, Ravi R, Singh M (2005) On two-stage stochastic minimum spanning trees. Springer, Berlin, pp 321–334
Swamy C, Shmoys DB (2006) Algorithms column: approximation algorithms for 2-stage stochastic optimization problems. ACM SIGACT News 37(1):1–16
Gallager RG, Humblet PA, Spira PM (1983) A distributed algorithm for minimum weight spanning trees. ACM Trans Program Lang Syst 5:66–77
Spira P (1977) Communication complexity of distributed minimum spanning tree algorithms. In: Proceedings of the second Berkeley conference on distributed data management and computer networks
Dalal Y (April 1977) Broadcast protocols in packet switched computer networks. Technical Report 128. Department of Electrical Engineering, Stanford University, Stanford
Gafni E (1985) Improvements in the time complexity of two message-optimal election algorithms. In: Proceedings of the 4th symposium on principles of distributed computing (PODC), pp 175–185
Awerbuch B (1987) Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems. In: Proceedings of the 19th ACM symposium on theory of computing (STOC), pp 230–240
Garay J, Kutten S, Peleg D (1998) A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J Comput 27:302–316
Kutten S, Peleg D (1998) Fast distributed construction of k-dominating sets and applications. J Algorithms 28:40–66
Elkin M (2004) A faster distributed protocol for constructing minimum spanning tree. In: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), pp. 352–361
Peleg D, Rabinovich V (1999) A near-tight lower bound on the time complexity of distributed MST construction. In: Proceedings of the 40th IEEE symposium on foundations of computer science (FOCS), pp 253–261
Elkin M (2004) Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In: Proceedings of the ACM symposium on theory of computing (STOC), pp 331–340
Elkin M (2004) An overview of distributed approximation. ACM SIGACT News 35(4):40–57
Khan M, Pandurangan G (2006) A fast distributed approximation algorithm for minimum spanning trees. In: Proceedings of the 20th international symposium on distributed computing (DISC)
Aggarwal V, Aneja Y, Nair K (1982) Minimal spanning tree subject to a side constraint. Comput Oper Res 9:287–296
Gruber M, Hemert J, Raidl GR (2006) Neighborhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA and ACO. In: Proceedings of genetic and evolutionary computational conference (GECCO’2006)
Bui TN, Zrncic CM (2006) An ant-based algorithm for finding degree-constrained minimum spanning tree. In: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp 11–18
Oncan T (2007) Design of capacitated minimum spanning tree with uncertain cost and demand parameters. Inf Sci 177:4354–4367
Oencan T, Cordeau JF, Laporte G (2008) A tabu search heuristic for the generalized minimum spanning tree problem. Eur J Oper Res 191(2):306–319
Parsa M, Zhu Q, Garcia-Luna-Aceves JJ (1998) An iterative algorithm for delay-constrained minimum-cost multicasting. IEEE/ACM Trans Netw 6(4):461–474
Salama HF, Reeves DS, Viniotis Y (1997) The Delay-constrained minimum spanning tree problem. In: Proceedings of the second IEEE symposium on computers and communications, pp 699–703
Gouveia L, Simonetti L, Uchoa E (2009) Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. J Math Program (in press)
Sharaiha YM, Gendreau M, Laporte G, Osman IH (1998) A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29(3):161–171
Hanr L, Wang Y (2006) A novel genetic algorithm for degree-constrained minimum spanning tree problem. Int J Comput Sci Netw Secur 6(7A):50–57
Krishnamoorthy M, Ernst A (2001) Comparison of algorithms for the degree constrained minimum spanning tree. J Heurist 7:587–611
Doulliez P, Jamoulle E (1972) Transportation networks with random arc capacities. RAIRO Oper Res 3:45–60
Hutson KR, Shier DR (2005) Bounding distributions for the weight of a minimum spanning tree in stochastic networks. Oper Res 53(5):879–886
Thathachar MAL, Harita BR (1987) Learning automata with changing number of actions. IEEE Trans Syst Man Cybern SMG17:1095–1100
Narendra KS, Thathachar KS (1989) Learning automata: an introduction. Printice-Hall, New York
Lakshmivarahan S, Thathachar MAL (1976) Bounds on the convergence probabilities of learning automata. IEEE Trans Syst Man Cybern SMC-6:756–763
Gower JC, Ross GJS (1969) Minimum spanning trees and single linkage cluster analysis. J R Stat Soc 18(1): 54–64
Barzily Z, Volkovich Z, Akteke-Öztürk B, Weber GW (2009) On a minimal spanning tree approach in the cluster validation problem. Informatica 20(2):187–202
Marchand-Maillet S, Sharaiha YM (1996) A minimum spanning tree approach to line image analysis. In: Proceedings of 13th international conference on pattern recognition (ICPR’96), p 225
Li J, Yang S, Wang X, Xue X, Li B (2009) Tree-structured data regeneration with network coding in distributed storage systems. In: Proceedings of international conference on image processing, Charleston, USA, pp 481–484
Kang ANC, T Lee RC, Chang CL, Chang SK (1977) Storage reduction through minimal spanning trees and spanning forests. IEEE Trans Comput C-26:425–434
Osteen RE, Lin PP (1974) Picture skeletons based on eccentricities of points of minimum spanning trees. SIAM J Comput 3:23–40
Graham RL, Hell P (1985) On the history of the minimum spanning tree problem. IEEE Ann Hist Comput 7(1):43–57
Jain A, Mamer JW (1988) Approximations for the random minimal spanning tree with applications to network provisioning. Oper Res 36:575–584
Torkestani Akbari J, Meybodi MR (2010) Learning automata-based algorithms for finding minimum weakly connected dominating set in stochastic graphs. Int J Uncertain Fuzziness Knowl-Based Syst (to appear)
Torkestani Akbari J, Meybodi MR (2010) Mobility-based multicast routing algorithm in wireless mobile ad hoc networks: a learning automata approach. J Comput Commun 33:721–735
Torkestani Akbari J, Meybodi MR (2010) A new vertex coloring algorithm based on variable action-set learning automata. J Comput Inf 29(3):1001–1020
Torkestani Akbari J, Meybodi MR (Feb. 2010) Weighted steiner connected dominating set and its application to multicast routing in wireless MANETs, Wireless personal communications, Springer, Berlin
Torkestani Akbari J, Meybodi MR (2010) An efficient cluster-based cdma/tdma scheme for wireless mobile ad-hoc networks: a learning automata approach. J Netw Comput Appl 33:477–490
Torkestani Akbari J, Meybodi MR (2010) Clustering the wireless ad-hoc networks: a distributed learning automata approach. J Parallel Distrib Comput 70:394–405
Torkestani Akbari J, Meybodi MR (2010) An intelligent back bone formation algorithm in wireless ad hoc networks based on distributed learning automata. J Comput Netw 54:826–843
Billard EA, Lakshmivarahan S (1999) Learning in multi-level games with incomplete information. Part I. IEEE Trans Syst Man Cybern-Part B: Cybern 19:329–339
Meybodi MR (1983) Learning automata and its application to priority assignment in a queuing system with unknown characteristics, Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of Oklahoma, Norman, Oklahoma, USA
Hashim AA, Amir S, Mars P (1986) Application of learning automata to data compression In: Narendra KS (ed.) Adaptive and learning systems. Plenum, New York, pp 229–234
Oommen BJ, Hansen ER (Aug. 1987) List organizing strategies using stochastic move-to-front and stochastic move-to-rear operations. SIAM J Comput 16:705–716
Unsal C, Kachroo P, Bay JS (1999) Multiple stochastic learning automata for vehicle path control in an automated highway system. IEEE Trans Syst Man Cybern-Part A 29:120–128
Barto AG, Anandan P (1985) Pattern-recognizing stochastic learning automata. IEEE Trans Syst Man Cybern SMC-15:360–375
Akbari Torkestani J, Meybodi MR (2010) A learning automata-based cognitive radio for clustered wireless ad-hoc networks. J. Netw. Syst. Manag. (to appear)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Akbari Torkestani, J., Meybodi, M.R. A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs. J Supercomput 59, 1035–1054 (2012). https://doi.org/10.1007/s11227-010-0484-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-010-0484-1