A fast algorithm for computing minimum routing cost spanning trees

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

Rui Campos (Autor) Outra; Manuel Ricardo (Autor) FEUP

Revista

Título: Computer Networks

Vol. 52 Nº 17

Páginas: 3229-3247

ISSN: 1389-1286

Editora: Elsevier

Indexação

ISI Web of Knowledge - 22 Citações

Scopus - 26 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

CORDIS: Ciências Tecnológicas > Engenharia > Engenharia de comunicações > Engenharia de telecomunicações

Outras Informações

ID Authenticus: P-003-T9A

DOI: 10.1016/j.comnet.2008.08.013

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19