Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 13 / Issue 11

available in:   PDF (156 kB) PS (154 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-013-11-1501


Spectral Densest Subgraph and Independence Number of a Graph

Reid Andersen (Microsoft Research, USA)

Sebastian M. Cioabă (University of California, USA)

Abstract: In this paper, we study spectral versions of the densest subgraph problem and the largest independence subset problem. In the first part, we give an algorithm for identifying small subgraphs with large spectral radius. We also prove a Hoffman-type ratio bound for the order of an induced subgraph whose spectral radius is bounded from above.

Keywords: densest subgraph, eigenvalues, graphs, independence number

Categories: F.4.1