An Algorithm to Find the Directed Minimum Spanning Trees
DOI:
https://doi.org/10.26438/ijcse/v7i9.233239Keywords:
Wireless networks, mobile networks, multicast, evolving graphs, LEO satellites, minimum spanning trees, strongly connected components, graph theoretic models, NP-completeAbstract
New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks that have highly dynamic behaviour. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the network topology are hard to be effectively captured in a classical graph model. In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristic of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks. We first show that computing different types of strongly connected components in this model in NP-Complete, and then propose an algorithm to build all rooted directly minimum spanning trees in already identified strongly connected components.
References
[1]. Y. J Chu amd T H. Liu. On the shortest arborescence of a directed graph. Science Sincia, 14:1396- 1400, 1965
[2]. T. Cormen, C. Leiserson and R. Rivest. Introduction to Algorithms. The MIT Press, 1990
[3]. C.Scheideler. Models and techniques for communication in dunamic networks. In In H. Alt and A. Ferreira, editors, Proceedings of the 19th International Symposium on Theoretical Aspecys of Computer Science, volume 2285, pages 27-19. Springer-Verlag, March 2002.
[4]. E. Ekici, I. F Akyildiz, and M. D. Bender. Datagram routing algorithm for LEO satellite networks. In IEEE infocom, pages 500-508,2000.
[5]. Ferreira, on models and algorithms for dmanic communication networks: The case for evolving graphs. In Proceedings of 4e rencontres francophnes sur les Aspects Algorithmiques des Telecommunications (ALGOTEL ’2002), Meze, France, May 2002.
[6]. Fereira, J. Galtier, and P. Penna. Topological design, routing and handover in satellite networks. In I. Stojmenovic, editor, Handbook of wireless Networks and Mobile Computing, pages 473-493, John Wiley and Sons, 2002.
[7]. P. A Humblet. A distributed algorithm for minimum weight directed spanning trees. IEEE transactions on communications, COM-31(6): 756-762, 1983.
[8]. R. E. Tarjan. Finding optimum branching. Networks, pages 25-35, 1977.
[9]. P.-J. Wan, G, Calinescue, X. Li, and O. Frieder. Minimum-energy broadcast routing in static ad hoc wireless networks. In Proc. IEEE infocom, pages 1162-1171, Anchorage Alaska, 2001.
[10]. M. Werner and G. Maral. Traffic flows and dynamic routing in leo intersatellite link networks. In In Proceedings 5th International Mobile Satellite Conference (IMSC ’97), Pasadena, California, USA, June 1997.
[11]. M. Werner and F. Wauquiez. Capacity dimensioning of ISL networks in broadband LEO satellite systems. In sixth International Mobile Satellite Conference : IMSC ’99, pages 334-341, Ottawa, Canada, June 1999.
[12]. J. Wieselthier, G. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In proc. IEEE infocom, pages585-594, Tel Aviv, 2000.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
