Spectral techniques in graph algorithms

被引：34

作者：

Alon, N ^{[1
]}

机构：

[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel

来源：

LATIN '98: THEORETICAL INFORMATICS | 1998年 / 1380卷

关键词：

D O I：

10.1007/BFb0054322

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The existence of efficient algorithms to compute the eigenvectors and eigenvalues of graphs supplies a useful tool for the design of various graph algorithms. In this survey we describe several algorithms based on spectral techniques focusing on their performance for randomly generated input graphs.

引用

页码：206 / 215

页数：10

共 53 条

[1] THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS [J].

ALON, N ;

BOPPANA, RB .

COMBINATORICA, 1987, 7 (01) :1-22

[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]

Alon N., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P346, DOI 10.1145/195058.195187

[5]

Alon N., 1984, P 25 ANN S FDN COMP, P320

[6]

ALON N, 1998, IN PRESS P 9 ANN ACM

[7]

ALON N, 1992, PROBABILISTIC METHOD

[8]

ALON N, IN PRESS SIAM J COMP

[9]

ALON N, 1902, IN PRESS MATH PROGRA

[10]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

← 1 2 3 4 5 6 →