Graph Weight Allocation to Meet Laplacian Spectral Constraints

  • 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.

  • 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}
}