No Access

LEARNING AUTOMATA-BASED ALGORITHMS FOR FINDING MINIMUM WEAKLY CONNECTED DOMINATING SET IN STOCHASTIC GRAPHS

JAVAD AKBARI TORKESTANI

Islamic Azad University, Arak Branch, Young Researchers Club, Arak, Iran

Search for more papers by this author

and

MOHAMMAD REZA MEYBODI

Department of Computer Engineering and IT, Amirkabir University of Technology, Tehran, Iran

Search for more papers by this author

https://doi.org/10.1142/S0218488510006775Cited by:21 (Source: Crossref)

Abstract

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.

Keywords:

References

Y. P. Chen and A. L. Liestman, Ad Hoc Networks 3, 629 (2005). Crossref, Google Scholar
B. Han and W. Jia, J. Parallel and Distributed Computing 67, 727 (2007), DOI: 10.1016/j.jpdc.2007.03.001. Crossref, Web of Science, Google Scholar
R. Rajaraman, SIGACT News 33(2), 60 (2002), DOI: 10.1145/564585.564602. Crossref, Google Scholar
Y. Z. Chen and A. L. Listman, Approximating minimum size weakly connected dominating sets for clustering mobile ad hoc networks, Proc. Third ACM Int. Symp. Mobile Ad Hoc Networking and Computing (MobiHoc'2002) pp. 157–164. Google Scholar
Y. P. Chen and A. L. Liestman, Int. J. Foundations of Computer Science 14(2), 305 (2003), DOI: 10.1142/S0129054103001741. Link, Web of Science, Google Scholar
K. M. Alzoubi, P. J. Wan and O. Frieder, Int. J. Foundations of Computer Science 14(2), 287 (2003), DOI: 10.1142/S012905410300173X. Link, Google Scholar
R. G. Gallager, P. A. Humblet and P. M. Spira, ACM Trans. Programming Languages and Systems 5, 66 (1983), DOI: 10.1145/357195.357200. Crossref, Web of Science, Google Scholar
S. Guha and S. Khuller, Algorithmica 20(4), 374 (1998), DOI: 10.1007/PL00009201. Crossref, Web of Science, Google Scholar
O. Dousse, F. Baccelli and P. Thiran, IEEE/ACM Trans. Networking 13(2), 425 (2005), DOI: 10.1109/TNET.2005.845546. Crossref, Web of Science, Google Scholar
S. Basagni, M. Mastrogiovanni and C. Petrioli, A performance comparison of protocols for clustering and backbone formation in large scale ad hoc network, Proc. First IEEE Int. Conf. Mobile Ad Hoc and Sensor Systems (MASS'2004) pp. 70–79. Google Scholar
B. Das and V. Bharghavan , Routing in ad-hoc networks using minimum connected dominating sets , IEEE Int. Conf. on Communications (ICC'97) . Google Scholar
I. Chlamtac and S. Kutten, IEEE Trans. Computing 36(10), 1209 (1987). Web of Science, Google Scholar
H. Lim and C. Kim, J. Computer Communications 24, 353 (2001), DOI: 10.1016/S0140-3664(00)00233-4. Crossref, Web of Science, Google Scholar
X. Chenget al., J. Wireless Communications and Mobile Computing 6, 183 (2006), DOI: 10.1002/wcm.378. Crossref, Web of Science, Google Scholar
J. Wu, B. Wu and I. Stojmenovic, J. Wireless Communications and Mobile Computing 3, 425 (2003), DOI: 10.1002/wcm.125. Crossref, Web of Science, Google Scholar
S. Basagni, D. Bruschi and I. Chlamtac, IEEE/ACM Trans. Networking 7(6), 799 (1999), DOI: 10.1109/90.811446. Crossref, Web of Science, Google Scholar
R. Ghosh and S. Basagni, J. Wireless Communications and Mobile Computing 8, 295 (2008), DOI: 10.1002/wcm.578. Crossref, Web of Science, Google Scholar
F. D. Tolba , D. Magoni and P. Lorenz , A stable clustering algorithm for highly mobile ad hoc networks , Second Int. Conf. Systems and Networks Communications (ICSNC 2007) . Google Scholar
Y. X. Wang and F. S. Bao , An entropy-based weighted clustering algorithm and its optimization for ad hoc networks , Third IEEE Int. Conf. Wireless and Mobile Computing, Networking and Communications (WiMob 2007) . Google Scholar
Z. E. Bazzalet al., A flexible weight based clustering algorithm in mobile ad hoc networks, Proc. Int. Conf. Systems and Networks Communication (ICSNC 2006) pp. 50–56. Google Scholar
T. N. Janakiraman and J. L. Rani, An efficient K-hop weighted domination clustering algorithm for mobile ad hoc networks using ranking, Int. Conf. Computational Intelligence and Multimedia Applications pp. 322–326. Google Scholar
W. D. Yang and G. Z. Zhang , A weight-based clustering algorithm for mobile ad hoc network , Proc. Third Int. Conf. on Wireless and Mobile Communications (ICWMC 2007) . Google Scholar
W. Choi and M. Woo, A distributed weighted clustering algorithm for mobile ad hoc networks, in Proc. Advanced Int. Conf. Telecommunications and Int. Conf. Internet and Web Applications and Services (AICT/ICIW 2006), 2006 . Google Scholar
R. Mellier and J. F. Myoupo , A weighted clustering algorithm for mobile ad hoc networkswith non unique weights , Int. Conf. Wireless and Mobile Communications (ICWMC 2006) . Google Scholar
M. Gerla and J. T.-C. Tsai, J. Wireless Networks 1(3), 255 (1995), DOI: 10.1007/BF01200845. Crossref, Web of Science, Google Scholar
J. E. Dunbaret al., Discrete Mathematics 167–168, 261 (1997). Crossref, Web of Science, Google Scholar
B. Han and W. Jia, J. Parallel and Distributed Computing 67, 727 (2007), DOI: 10.1016/j.jpdc.2007.03.001. Crossref, Web of Science, Google Scholar
I. Chlamtac, M. Conti and J. Liu, J. Ad Hoc Networks 1, 13 (2003), DOI: 10.1016/S1570-8705(03)00013-1. Crossref, Web of Science, Google Scholar
S. Basagni et al. , Mobile Ad Hoc Networking ( IEEE Press , 2004 ) . Crossref, Google Scholar
B. N. Clark, C. J. Colbourn and D. S. Johnson, Discrete Mathematics 86, 165 (1990), DOI: 10.1016/0012-365X(90)90358-O. Crossref, Web of Science, Google Scholar
M. V. Maratheet al., Networks 25, 59 (1995), DOI: 10.1002/net.3230250205. Crossref, Web of Science, Google Scholar
K. S. Narendra and K. S. Thathachar , Learning Automata: An Introduction ( Prentice-Hall , New York , 1989 ) . Google Scholar
M. A. L. Thathachar and P. S. Sastry, Information Science 42, 743 (1997). Google Scholar
M. A. L. Thathachar and B. R. Harita, IEEE Trans. Systems, Man, and Cybernetics SMG17, 1095 (1987). Google Scholar
M. A. L. Thathachar and V. V. Phansalkar, IEEE Trans. Systems, Man and Cybernetics 24, 1459 (1995). Google Scholar
S. Lakshmivarahan and M. A. L. Thathachar, IEEE Trans. Systems, Man, and Cybernetics SMC-6, 756 (1976). Web of Science, Google Scholar
K. S. Narendra and M. A. L. Thathachar, IEEE Trans. Systems, Man, and Cybernetics SMC-l0(5), 262 (1980). Google Scholar
H. Beigy and M. R. Meybodi, Int. J. Uncertainty, Fuzziness and Knowledge-Based Systems 14, 591 (2006), DOI: 10.1142/S0218488506004217. Link, Web of Science, Google Scholar
J. Akbari Torkestani and M. R. Meybodi, J. Computing and Informatics 29(3), 447 (2010). Web of Science, Google Scholar
J. Akbari Torkestani and M. R. Meybodi , Graph coloring problem based on learning automata , Proc. Int. Conf. Information Management and Engineering (ICIME 2009) . Google Scholar
J. Akbari Torkestani and M. R. Meybodi , Approximating the minimum connected dominating set in stochastic graphs based on learning automata , Proc. Int. Conf. Information Management and Engineering (ICIME 2009) . Google Scholar
J. Akbari Torkestani and M. R. Meybodi , Solving the minimum spanning tree problem in stochastic graphs using learning automata , Proc. Int. Conf. Information Management and Engineering (ICIME 2009) . Google Scholar
J. Akbari Torkestani and M. R. Meybodi, J. Computer Communications 33(6), 721 (2010). Crossref, Web of Science, Google Scholar
J. Akbari Torkestani and M. R. Meybodi , Wireless Personal Communications ( Springer Publishing Company , 2010 ) . Google Scholar
J. Akbari Torkestani and M. R. Meybodi, J. Network and Computer Applications 33(4), 477 (2010). Crossref, Web of Science, Google Scholar
J. Akbari Torkestani and M. R. Meybodi, J. Parallel and Distributed Computing 70(4), 394 (2010). Crossref, Web of Science, Google Scholar
J. Akbari Torkestani and M. R. Meybodi, J. Computer Networks 54(5), 826 (2010). Crossref, Web of Science, Google Scholar
S. Lakshmivarahan and K. S. Narendra, SIAM J. Control Optim. 20, 541 (1982), DOI: 10.1137/0320039. Crossref, Web of Science, Google Scholar
K. R. Hutson and D. R. Shier, Annals of Operations Research 146 (Springer, 2006) pp. 3–18. Google Scholar
S. Holm, Scandinavian J. Statistics 6, 65 (1979). Web of Science, Google Scholar
Http://dimacs.rutgers.edu/Challenges . Google Scholar
F. B. ALT, Encyclopedia of Statistical Sciences 1, 294 (1982). Web of Science, Google Scholar
C. E. Bonferroni, Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commerciali di Firenze 8, 3 (1936). Google Scholar
J. Akbari Torkestani and M. R. Meybodi , Journal of Network and Systems Management ( Springer Publishing Company , 2010 ) . Google Scholar
J. Akbari Torkestani and M. R. Meybodi , Journal of Supercomputing ( Springer Publishing Company , 2010 ) . Google Scholar