Change search
ReferencesLink to record
Permanent link

Direct link
Distributed algebraic connectivity estimation for undirected graphs with upper and lower bounds
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-7309-8086
Show others and affiliations
2014 (English)In: Automatica, ISSN 0005-1098, Vol. 50, no 12, 3253-3259 p.Article in journal (Refereed) Published
Abstract [en]

The algebraic connectivity of the graph Laplacian plays an essential role in various multi-agent control systems. In many cases a lower bound of this algebraic connectivity is necessary in order to achieve a certain performance. Lately, several methods based on distributed Power Iteration have been proposed for computing the algebraic connectivity of a symmetric Laplacian matrix. However, these methods cannot give any lower bound of the algebraic connectivity and their convergence rates are often unclear. In this paper, we present a distributed algorithm for estimating the algebraic connectivity for undirected graphs with symmetric Laplacian matrices. Our method relies on the distributed computation of the powers of the adjacency matrix and its main interest is that, at each iteration, agents obtain both upper and lower bounds for the true algebraic connectivity. Both bounds successively approach the true algebraic connectivity with the convergence speed no slower than O(1/k).

Place, publisher, year, edition, pages
2014. Vol. 50, no 12, 3253-3259 p.
Keyword [en]
Multi-agent systems, Control of networks, Sensor networks, Algebraic connectivity
National Category
Control Engineering
URN: urn:nbn:se:kth:diva-159987DOI: 10.1016/j.automatica.2014.10.051ISI: 000347760100032ScopusID: 2-s2.0-84919435363OAI: diva2:790775

QC 20150225

Available from: 2015-02-25 Created: 2015-02-12 Last updated: 2015-03-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Dimarogonas, Dimos V.Johansson, Karl Henrik
By organisation
Automatic ControlACCESS Linnaeus Centre
In the same journal
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 55 hits
ReferencesLink to record
Permanent link

Direct link