Efficient Computation of the Characteristic Polynomial of a Threshold Graph.

An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chvátal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one vertex graph by repeatedly adding either an isolated vertex or a dominating vertex, which is a vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of O ( n log 2 ź n ) for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time. We improve the running time drastically in the case where there is a small number of alternations between 0's and 1's in the sequence defining a threshold graph. A simple recurrence equation for the determinant of a weighted threshold graph matrix is presented.The characteristic polynomial is computed in O ( n log 2 ź n ) arithmetic operations.The algorithm is more efficient if the alternations in the defining sequence are o ( n ) .As the numbers may be of length n log ź n , the bit complexity is investigated too.