Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
11024727 | Linear Algebra and its Applications | 2019 | 27 Pages |
Abstract
Finding a diagonal matrix congruent to AâcI for constants c, where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k-expression is known, then diagonalization can be done in time O(poly(k)n) where n is the order of G.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Martin Fürer, Carlos Hoppen, David P. Jacobs, Vilmar Trevisan,