Spectral techniques in graph algorithms

DOI10.1007/BFB0054322MaRDI QIDQ3839004zbMATH OpenFDO

Authors Noga Alon

Publication date 25 October 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054322

zbMATH Keywords

eigenvalueseigenvectorsgraph algorithmsgraph bisectiongraph coloringLaplace matricesNP-hardrandom graphspectral techniques

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

The existence of efficient algorithms for computing the eigenvectors and eigenvalues of graphs supplies a useful tool for the design of various graph algorithms. This paper demonstrates the relevance of spectral techniques to the graph bisection, graph coloring and finding the independence number of a graph. All of the problems are NP-hard and even the task of finding a good approximate solution for each of them is hard to achieve. Spectral techniques based on the eigenvalues and eigenvectors of the adjacency or the Laplace matrices of graphs, can provably solve the above problems for various classes of randomly generated graphs, where all previous techniques failed. This is mostly a survey paper and hence the focus is on the underlying ideas and not on the detailed proofs. For the entire collection see [Zbl 0889.00032].

Recommendations

• Graph spectral techniques in computer sciences
• Graph spectra in computer science
• scientific article; zbMATH DE number 2149405
• scientific article; zbMATH DE number 964896
• Spectral sparsification of graphs
• Spectral techniques applied to sparse random graphs
• scientific article; zbMATH DE number 5578782
• Graph spectra
• Spectra of graphs
• scientific article; zbMATH DE number 1219775

Cited in

(14)

• Spectral methods for graph bisection problems.
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• Graph-based algorithms for phase-type distributions
• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
• Spectral radii of sparse random matrices
• Approximating independent set in perturbed graphs
• Graph spectral techniques in computer sciences
• Sharp spectral bounds of several graph parameters using eigenvector norms
• Graph Coloring Using Eigenvalue Decomposition
• Spectral algorithms
• scientific article; zbMATH DE number 2087126 (Why is no real title available?)
• The spectral edge of constant degree Erdős-Rényi graphs
• Community detection in sparse networks via Grothendieck's inequality

This page was built for publication: Spectral techniques in graph algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3839004)