Computing the Characteristic Polynomial of Threshold Graphs
David P. Jacobs, Vilmar Trevisan, and Fernando Tura
Vol. 18, no. 5, pp. 709-719, 2014. Regular paper.
Abstract 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).
Submitted: December 2013.
Reviewed: October 2014.
Revised: November 2014.
Accepted: December 2014.
Final: December 2014.
Published: December 2014.
Communicated by Martin F├╝rer
article (PDF)