摘要: We focus on efficient protocols that enhance a network with topology awareness. discuss centralized algorithms provable performance, and introduce decentralized asynchronous heuristics use only local information computations. These are based distributed solutions of convex programs expressing optimization various spectral properties the matrix associated graph topology. For example, these assign special weights to links crossing or directed towards small cuts by minimizing second eigenvalue. Our main technical ingredient is perform computations in manner preserves critical invariants exact eigenvalue adjacency
sci-hub.se 参考文章(13)
Alistair Sinclair, Algorithms for Random Generation and Counting: A Markov Chain Approach ,(1993)
Fan R K Chung, Spectral Graph Theory ,(1996)
Arpita Ghosh, Stephen Boyd, Amin Saberi, Minimizing Effective Resistance of a Graph Siam Review. ,vol. 50, pp. 37- 66 ,(2008) , 10.1137/050645452
Sanjeev Arora, Satish Rao, Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning symposium on the theory of computing. pp. 222- 231 ,(2004) , 10.1145/1007352.1007355
Tomas Feder, Adam Guetz, Milena Mihail, Amin Saberi, A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks foundations of computer science. pp. 69- 76 ,(2006) , 10.1109/FOCS.2006.5
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker, Search and replication in unstructured peer-to-peer networks measurement and modeling of computer systems. ,vol. 30, pp. 258- 259 ,(2002) , 10.1145/511334.511369
Martin Dyer, Catherine Greenhill, Colin Cooper, Sampling regular graphs and a peer-to-peer network symposium on discrete algorithms. pp. 980- 988 ,(2005) , 10.5555/1070432.1070574
Daniel A. Spielman, Shang-Hua Teng, Spectral partitioning works: planar graphs and finite element meshes foundations of computer science. pp. 96- 105 ,(1996) , 10.1109/SFCS.1996.548468
C. Gkantsidis, M. Mihail, E. Zegura, Spectral analysis of Internet topologies international conference on computer communications. ,vol. 1, pp. 364- 374 ,(2003) , 10.1109/INFCOM.2003.1208688
T. Leighton, S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science. pp. 422- 431 ,(1988) , 10.1109/SFCS.1988.21958