期刊
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
卷 55, 期 1, 页码 170-174出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2009.2033763
关键词
Algebraic connectivity; Laplacian matrix
资金
- University of Stellenbosch, South Africa
For a given graph (or network) G, consider another graph G' by adding or deleting an edge e to or from G. We propose a computationally efficient algorithm of finding e such that the second smallest eigenvalue (algebraic connectivity, lambda(2) (G')) of G' is maximized or minimized. Theoretically, the proposed algorithm runs in O(4mnlog(d/epsilon)), where n is the number of nodes in G, m is the number of disconnected edges in G, d is the difference between lambda(3) (G) and lambda(2) (G), and epsilon > 0 is a sufficiently small constant. However, extensive simulations show that the practical computational complexity of the proposed algorithm, O(5.7 mm), is nearly comparable to that of a simple greedy- type heuristic, O(2mn). This algorithm can also be easily modified for finding e which affects lambda(2) the least.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据