A History of Spectral Graph Theory and its Applications, Part II
Автор: GraphXD: Graphs Across Domains
Загружено: 2018-04-05
Просмотров: 1163
Описание:
Aaron Schild (Computer Science, UC Berkeley)
Spectral graph theory started in the 80s, when Cheeger’s inequality was used as a means for constructing sparse and balanced cuts in a graph. In the 2000s, our field moved on from studying specific eigenvalues to studying the whole spectrum of the Laplacian matrix with fast Laplacian solvers. To obtain fast Laplacian solvers, we needed to sparsify graphs, for which we exploited concentration phenomena of random matrices. In the 2010s, improvements to these tools led to improvements on a wide variety of problems, like maximum flow, travelling salesman (both symmetric and asymmetric), and random spanning tree generation. In this talk, we briefly survey this chain of events and suggest some future directions.
License: CC BY-NC-SA 4.0
https://creativecommons.org/licenses/...
Повторяем попытку...
Доступные форматы для скачивания:
Скачать видео
-
Информация по загрузке:
