{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T12:01:27Z","timestamp":1747224087628,"version":"3.40.5"},"reference-count":23,"publisher":"IGI Global","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,10,1]]},"abstract":"<p>Multimedia applications are expected to guarantee end-to-end quality of service (QoS) and are characterized by stringent constraints on delay, delay-jitter, bandwidth, cost, and so forth. The authors observe that Kruskal\u2019s algorithm is limited to minimal (maximal) spanning unconstrained tree. As such, the authors extend Kruskal\u2019s algorithm to incorporate the delay bound constraint. Consequently, a novel algorithm is proposed, called EKRUS (Extended Kruskal), for constructing multicast trees. The EKRUS\u2019 distinguishing features consists of a better management of Kruskal\u2019s priority queues, and in the provision of edge priority aggregation. Preliminary results show that the proposed EKRUS algorithm performs as well as the best-known algorithms (such as the DDMC, DMCTc algorithms) while exhibiting reduced complexity. The authors conducted an intensive analysis and evaluations of different strategies of assigning edges into the classes of the queue as well as edge selection. As a result, the EKRUS algorithm was further extended with different edge assignment and selection strategies. Through extensive simulations, the authors have evaluated various versions of the EKRUS and analyzed their performance under different load conditions.<\/p>","DOI":"10.4018\/jbdcn.2011100103","type":"journal-article","created":{"date-parts":[[2011,11,16]],"date-time":"2011-11-16T12:46:29Z","timestamp":1321447589000},"page":"32-51","source":"Crossref","is-referenced-by-count":1,"title":["New Strategies and Extensions in Kruskal\u2019s Algorithm in Multicast Routing"],"prefix":"10.4018","volume":"7","author":[{"given":"Mohamed","family":"Aissa","sequence":"first","affiliation":[{"name":"University of Nizwa, Oman"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3617-7636","authenticated-orcid":true,"given":"Adel","family":"Ben Mnaouer","sequence":"additional","affiliation":[{"name":"Canadian University Dubai, UAE"}]},{"given":"Rion","family":"Murray","sequence":"additional","affiliation":[{"name":"University of Trinidad and Tobago, Trinidad and Tobago"}]},{"given":"Abdelfettah","family":"Belghith","sequence":"additional","affiliation":[{"name":"HANA Research Group University of Manouba, Tunisia"}]}],"member":"2432","reference":[{"key":"jbdcn.2011100103-0","unstructured":"Alpert, C. J., Hu, T. C., & Huang, J. H. (1993). A direct combination of the Prim and Dijkstra constructions for improved performance-driven global routing. In Proceedings of the IEEE International Symposium on Circuit and Systems, Chicago, IL (pp. 1869-1872)."},{"key":"jbdcn.2011100103-1","unstructured":"Chenghui, Y., & Chunanjun, R. (2010). Simulation research of communication networks based on Prim algorithm. In Proceedings of the International Forum on Information Technology and Applications."},{"journal-title":"Introduction to algorithms","year":"2001","author":"T. H.Cormen","key":"jbdcn.2011100103-2"},{"key":"jbdcn.2011100103-3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"issue":"2","key":"jbdcn.2011100103-4","article-title":"QDMR, an efficient QoS dependent multicast routing algorithm.","volume":"2","author":"L.Guo","year":"2000","journal-title":"Journal of Communications and Networks"},{"key":"jbdcn.2011100103-5","doi-asserted-by":"crossref","unstructured":"Guttoski, P. B., Sunye, M. S., & Silva, F. (2007). Kruskal's algorithm for query tree optimization. In Proceedings of the 11th International Database Engineering and Applications Symposium.","DOI":"10.1109\/IDEAS.2007.4318118"},{"key":"jbdcn.2011100103-6","first-page":"823","article-title":"A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks.","volume":"6","author":"X.Jia","year":"1998","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"jbdcn.2011100103-7","doi-asserted-by":"crossref","unstructured":"Kershenbaum, A., & Van Styke, R. (1972). Computing minimum spanning trees efficiently. In Proceedings of the ACM Annual Conference (Vol. 1, pp. 518-527).","DOI":"10.1145\/800193.569966"},{"key":"jbdcn.2011100103-8","doi-asserted-by":"crossref","unstructured":"Kompella, V. P., Pasquale, J. C., & Polyzos, G. C. (1993, June). Two distributed algorithms for multicasting multimedia information. In Proceedings of the International Conference on Computer Communications and Networks, San Diego, CA (pp. 343-349).","DOI":"10.1109\/INFCOM.1992.263480"},{"key":"jbdcn.2011100103-9","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"jbdcn.2011100103-10","unstructured":"Li, C., Raha, A., & Zhao, W. (1997), Stability in ATM networks. In Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies Driving the Information Revolution (pp. 160-167)."},{"journal-title":"Survey of adaptive shortest-path routing in dynamic packet-switched networks","year":"1997","author":"A. B.McDonald","key":"jbdcn.2011100103-11"},{"key":"jbdcn.2011100103-12","unstructured":"Meylan, F., Kiatake, L. G. G., Santos, M. Z., Kofuji, S. T., & Courtiat, J. P. (1999). Comparative analysis of multicast routing algorithms for multimedia communication over ATM networks. In Proceedings of the IEEE Latin American Network Operations and Management Symposium, Rio de Janeiro, Brazil."},{"key":"jbdcn.2011100103-13","first-page":"985","article-title":"A new delay-constrained algorithm for multicast routing tree construction.","author":"A.Mohamed","year":"2004","journal-title":"International Journal of Communication Systems"},{"key":"jbdcn.2011100103-14","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00323-4"},{"key":"jbdcn.2011100103-15","doi-asserted-by":"crossref","unstructured":"Pan, D., Liu, Z.-B., Ding, X.-F., & Zheng, Q. (2009). The application of union-find sets in Kruskal algorithm. In Proceedings of the International Conference on Artificial Intelligence and Computational Intelligence (pp. 159-162).","DOI":"10.1109\/AICI.2009.155"},{"key":"jbdcn.2011100103-16","doi-asserted-by":"publisher","DOI":"10.1007\/s005300050075"},{"key":"jbdcn.2011100103-17","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connecting networks and some generalizations.","volume":"36","author":"B. C.Prim","year":"1959","journal-title":"The Bell System Technical Journal"},{"key":"jbdcn.2011100103-18","doi-asserted-by":"publisher","DOI":"10.1109\/90.532865"},{"key":"jbdcn.2011100103-19","doi-asserted-by":"crossref","unstructured":"Salama, H. F. (1996). Multicast routing for real-time communication on high-speed networks (Doctoral dissertation). Raleigh, NC: North Carolina State University.","DOI":"10.1007\/978-0-387-34949-7_3"},{"key":"jbdcn.2011100103-20","unstructured":"Salama, H. F., et al. (1995). MCRSIM simulator source code and users' manual. Raleigh, NC: North Carolina State University. Retrieved from http:\/\/ftp.csc.ncsu.edu:\/pub\/rtcomm"},{"key":"jbdcn.2011100103-21","doi-asserted-by":"publisher","DOI":"10.1109\/49.564135"},{"key":"jbdcn.2011100103-22","unstructured":"Sun, Q., & Langendoerfre, H. (1995). Efficient multicast routing for delay-sensitive applications. In Proceedings of the 2nd Workshop on Protocols for Multimedia Systems (pp. 452-458)."}],"container-title":["International Journal of Business Data Communications and Networking"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=61350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T15:15:32Z","timestamp":1654096532000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jbdcn.2011100103"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2011,10,1]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,10]]}},"URL":"https:\/\/doi.org\/10.4018\/jbdcn.2011100103","relation":{},"ISSN":["1548-0631","1548-064X"],"issn-type":[{"type":"print","value":"1548-0631"},{"type":"electronic","value":"1548-064X"}],"subject":[],"published":{"date-parts":[[2011,10,1]]}}}