Spectral Densest Subgraph and Independence Number of a Graph
Дата
Авторы
Andersen,Reid
Cioabă,Sebastian
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
graphs , eigenvalues , densest subgraph , independence number