Spectral graph theory and its applications

被引：177

作者：

Spielman, Daniel A. ^{[1
]}

机构：

[1] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA

来源：

48TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2007年

关键词：

D O I：

10.1109/FOCS.2007.56

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will survey some of their applications.

引用

页码：29 / 38

页数：10

共 29 条

[1]

ALON, 1997, SICOMP SIAM J COMPUT

[2] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].

ALON, N ;

MILMAN, VD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88

[3] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

[4]

BABAI L, 1982, ACM S THEOR COMP, P310

[5]

BONACICH P, 1987, AM J SOCIOL, V92, P1170, DOI 10.1086/228631

[6]

Cheeger J., 1970, P PRINCETON C HONOR, P195

[7]

Chung F, 1997, C BOARD MATH SCI AM

[8]

Donath W. E., 1972, IBM Technical Disclosure Bulletin, V15, P938

[9] LOWER BOUNDS FOR PARTITIONING OF GRAPHS [J].

DONATH, WE ;

HOFFMAN, AJ .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1973, 17 (05) :420-425

[10]

FIEDLER M, 1975, CZECH MATH J, V25, P607

← 1 2 3 →