A fast algorithm for computing minimum routing cost spanning trees |
| |
| Affiliation: | 1. Department of Computer Science, Jinan University, Guangzhou, China;2. Facebook Inc., 7006 126th Ave NE, Kirkland, WA 98033, USA;3. South University of Science and Technology of China, Shenzhen, China;1. Joint Research Centre, European Commission, Via Enrico Fermi 2749, 21027 Ispra (VA), Italy;2. DEIOC, IUDR, Universidad de La Laguna, Facultad de Matemáticas, 4a planta Astrofisico Francisco Sánchez s/n, 38271 Santa Cruz de Tenerife, Spain;3. School of Information Systems, Computing and Mathematics, Brunel University, Uxbridge, Middlesex, UB8 3PH, United Kingdom;1. Department of Information and Communication Engineering, Sejong University, Gunja-dong 98, Gwangjin-gu, Seoul 143-747, Republic of Korea;2. Ship Convergence Platform Research Team, ETRI, Gajeongno 138, Yuseong-gu, Daejeon 305-700, Republic of Korea;1. IFPB, Instituto Federal de Educação, Ciência e Tecnologia da Paraíba, 256 Av. João da Mata, CEP: 58.015-020, João Pessoa, PB, Brazil.;2. UFF, Universidade Federal Fluminense, 156 R. Passo da Pátria, CEP: 24210-240, Niterói, RJ, Brazil.;3. LIA-UAPV, Université d’Avignon, 339 Chemin des Meinajaries, 84140, Avignon, France.;4. UFPB, Universidade Federal da Paraíba, R. dos Escoteiros, CEP: 58055-000, João Pessoa, PB, Brazil. |
| |
| Abstract: | Communication networks have been developed based on two networking approaches: bridging and routing. The convergence to an all-Ethernet paradigm in Personal and Local Area Networks and the increasing heterogeneity found in these networks emphasizes the current and future applicability of bridging. When bridging is used, a single active spanning tree needs to be defined. A Minimum Routing Cost Tree is known to be the optimal spanning tree if the probability of communication between any pair of network nodes is the same. Given that its computation is a NP-hard problem, approximation algorithms have been proposed.We propose a new approximation Minimum Routing Cost Tree algorithm. Our algorithm has time complexity lower than the fastest known approximation algorithm and provides a spanning tree with the same routing cost in practice. In addition, it represents a better solution than the current spanning tree algorithm used in bridged networks. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
