Graph Weight Allocation to Meet Laplacian Spectral Constraints

Download: .pdf

Authors: S. Yusef Shafi, Murat Arcak, and Laurent El Ghaoui.

Status: In IEEE Trans. Automatic Control, vol. 57, No. 7, July 2012.

Abstract: We adjust the node and edge weightings of graphs using convex optimization to impose bounds on their Laplacian spectra. First, we derive necessary and sufficient conditions that characterize the feasibility of spectral bounds given positive node and edge weightings. Synthesizing these conditions leads naturally to algorithms that exploit convexity to achieve several eigenvalue bounds simultaneously. The algorithms we propose apply to many graph design problems as well as multi-agent systems control. Finally, we suggest efficient ways to accommodate larger graphs, and show that dual formulations lead to substantial improvement in the size of graphs that can be addressed.

Related links: Designing Node and Edge Weights of a Graph to Meet Laplacian Eigenvalue Constraints.

Bibtex reference:

@article{SAE:12,
	Title = {Graph Weight Allocation to meet {L}aplacian Spectral Constraints},
	Author = {Y. Shafi and M. Arcak and L. {El Ghaoui}},
	Year = 2012,
	Month = jul,
	Journal = {{IEEE} Trans.\ Automatic Control}
}