Computing the Characteristic Polynomial of Threshold Graphs - Jacobs, David; Trevisan, Vilmar; Tura, Fernando (Journal of Graph Algorithms and Applications, 2014)
We present an algorithm for constructing the characteristic polynomial of a threshold graph's adjacency matrix. The algorithm is based on a diagonalization procedure that is easy to describe. It can be implemented using O(n) space and with running time O(n2).