Show simple item record

dc.contributor.authorOliva, G.en
dc.contributor.authorSetola, R.en
dc.contributor.authorHadjicostis, Christoforos N.en
dc.creatorOliva, G.en
dc.creatorSetola, R.en
dc.creatorHadjicostis, Christoforos N.en
dc.description.abstractThe distributed calculation of node eccentricities, graph radius and graph diameter are fundamental steps to tune network protocols (e.g., setting an adequate time-to-live of packets), to select cluster heads, or to execute distributed algorithms, which typically depend on these parameters. Most existing methods deal with undirected topologies and have high memory and/or bandwidth requirements (or simply provide a bound on the diameter to reduce such costs). Other approaches, instead, require nodes able to communicate with their neighbors on a point-to-point basis, thus requiring each node to be aware of its neighbors. In this paper, we consider strongly connected directed graphs or connected undirected graphs, and we develop an algorithm that takes advantage of the robustness and versatility of the max-consensus algorithm, and has low computational, memory and bandwidth requirements. Moreover, the agents communicate by broadcasting messages to their (out-) neighbors without requiring any knowledge on them or needing point-to-point communication capability. Specifically, each node has memory occupation proportional to the number of its neighbors, while the bandwidth for each link at each time instant is O(logn) bits, where n is the number of nodes. The completion time of the proposed algorithm is O(δn) for undirected graphs and O(n2) for directed graphs, where δ is the network diameter. © 2016 Elsevier B.V. All rights reserved.en
dc.sourceSystems and Control Lettersen
dc.subjectDistributed computer systemsen
dc.subjectParallel algorithmsen
dc.subjectNetwork protocolsen
dc.subjectGraph theoryen
dc.subjectDirected graphsen
dc.subjectDistributed algorithmsen
dc.subjectGraphic methodsen
dc.subjectBandwidth requirementen
dc.subjectClustering algorithmsen
dc.subjectDistributed calculationen
dc.subjectFinite time calculationsen
dc.subjectPoint-to-point communicationen
dc.subjectSpot weldingen
dc.titleDistributed finite-time calculation of node eccentricities, graph radius and graph diameteren
dc.description.issueJournal Articleen
dc.description.endingpage27Πολυτεχνική Σχολή / Faculty of EngineeringΤμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών / Department of Electrical and Computer Engineering
dc.source.abbreviationSyst Control Letten
dc.contributor.orcidHadjicostis, Christoforos N. [0000-0002-1706-708X]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record