 |
 |
 |
 |
9:00 AM-10:00 AM
Chair: Michael Molloy, University of Toronto, Canada
Room: Convocation Hall
The existence of efficient algorithms to compute the eigenvectors and eigenvalues of graphs supplies a useful tool for the design of various graph algorithms.
The speaker will describe several algorithms of this type, mentioning their application as approximation algorithms and focusing on their performance for randomly generated input graphs. The algorithmic problems considered include ones motivated by questions in scheduling and VLSI circuit design, like graph coloring and graph bisection, and the methods used combine algebraic, probabilistic and combinatorial techniques.
A representative recent result, obtained jointly with M. Krivelevich and B. Sudakov, is a spectral technique for finding efficiently a clique of size epsilon n � in a random graph on n vertices with a clique of this size placed in it randomly.
Noga Alon
Department of Mathematics, Tel-Aviv University, Israel and
Institute for Advanced Study, Princeton
|
|
|
|