Utilize este identificador para referenciar este registo: https://hdl.handle.net/1822/24670

TítuloFast distributed computation of distances in networks
Autor(es)Almeida, Paulo Sérgio
Baquero, Carlos
Cunha, Alcino
Data2012
EditoraIEEE
RevistaProceedings of the IEEE Conference on Decision and Control
Resumo(s)This paper presents a distributed algorithm to simultaneously compute the diameter, radius and node eccentricity in all nodes of a synchronous network. Such topological information may be useful as input to configure other algorithms. Previous approaches have been modular, progressing in sequential phases using building blocks such as BFS tree construction, thus incurring longer executions than strictly required. We present an algorithm that, by timely propagation of available estimations, achieves a faster convergence to the correct values. We show local criteria for detecting convergence in each node. The algorithm avoids the creation of BFS trees and simply manipulates sets of node ids and hop counts. For the worst scenario of variable start times, each node i with eccentricity ecc(i) can compute: the node eccentricity in diam(G)+ecc(i)+2 rounds; the diameter in 2 diam(G)+ecc(i)+2 rounds; and the radius in diam(G) + ecc(i) + 2 radius(G) rounds.
TipoArtigo em ata de conferência
DescriçãoComunicação publicada em "IEEE Conference on Decision & Control (CDC)", pag. 5215-5220
URIhttps://hdl.handle.net/1822/24670
ISBN978-1-4673-2065-8
DOI10.1109/CDC.2012.6426872
ISSN0743-1546
Versão da editorahttp://ieeexplore.ieee.org
Arbitragem científicayes
AcessoAcesso aberto
Aparece nas coleções:HASLab - Artigos em atas de conferências internacionais (texto completo)

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
cdc12-1.pdf300,86 kBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID