Spectral techniques in graph algorithms

Noga Alon

doi:10.1007/bfb0054322

Spectral techniques in graph algorithms

Noga Alon

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

47 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	LATIN 1998
Subtitle of host publication	Theoretical Informatics - 3rd Latin American Symposium, Proceedings
Editors	Cláudio L. Lucchesi, Arnaldo V. Moura
Publisher	Springer Verlag
Pages	206-215
Number of pages	10
ISBN (Print)	3540642757, 9783540642756
DOIs	https://doi.org/10.1007/bfb0054322
State	Published - 1998
Externally published	Yes
Event	3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 - Campinas, Brazil Duration: Apr 20 1998 → Apr 24 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1380
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd Latin American Symposium on Theoretical Informatics, LATIN 1998
Country/Territory	Brazil
City	Campinas
Period	4/20/98 → 4/24/98

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0054322

Cite this

Alon, N. (1998). Spectral techniques in graph algorithms. In C. L. Lucchesi, & A. V. Moura (Eds.), LATIN 1998: Theoretical Informatics - 3rd Latin American Symposium, Proceedings (pp. 206-215). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1380). Springer Verlag. https://doi.org/10.1007/bfb0054322

@inproceedings{f5514fcb40fb45c1a4d1b6f502b4f212,

title = "Spectral techniques in graph algorithms",

abstract = "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.",

author = "Noga Alon",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 ; Conference date: 20-04-1998 Through 24-04-1998",

year = "1998",

doi = "10.1007/bfb0054322",

language = "English (US)",

isbn = "3540642757",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "206--215",

editor = "Lucchesi, {Cl{\'a}udio L.} and Moura, {Arnaldo V.}",

booktitle = "LATIN 1998",

address = "Germany",

}

Alon, N 1998, Spectral techniques in graph algorithms. in CL Lucchesi & AV Moura (eds), LATIN 1998: Theoretical Informatics - 3rd Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1380, Springer Verlag, pp. 206-215, 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998 , Campinas, Brazil, 4/20/98. https://doi.org/10.1007/bfb0054322

Spectral techniques in graph algorithms. / Alon, Noga.
LATIN 1998: Theoretical Informatics - 3rd Latin American Symposium, Proceedings. ed. / Cláudio L. Lucchesi; Arnaldo V. Moura. Springer Verlag, 1998. p. 206-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1380).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Spectral techniques in graph algorithms

AU - Alon, Noga

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998.

PY - 1998

Y1 - 1998

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

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

UR - http://www.scopus.com/inward/record.url?scp=84949221689&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949221689&partnerID=8YFLogxK

U2 - 10.1007/bfb0054322

DO - 10.1007/bfb0054322

M3 - Conference contribution

AN - SCOPUS:84949221689

SN - 3540642757

SN - 9783540642756

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 206

EP - 215

BT - LATIN 1998

A2 - Lucchesi, Cláudio L.

A2 - Moura, Arnaldo V.

PB - Springer Verlag

T2 - 3rd Latin American Symposium on Theoretical Informatics, LATIN 1998

Y2 - 20 April 1998 through 24 April 1998

ER -

Spectral techniques in graph algorithms

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this