@inproceedings{8b30074503d24c0ea8d164237f2afe4b,
title = "Efficient computation of the characteristic polynomial of a threshold graph",
abstract = "An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chv{\'a}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 log2 n) for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time.",
author = "Martin F{\"u}rer",
note = "Funding Information: M. F{\"u}rer—Research supported in part by NSF Grant CCF-1320814. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 9th International Workshop on Frontiers in Algorithmics, FAW 2015 ; Conference date: 03-07-2015 Through 05-07-2015",
year = "2015",
doi = "10.1007/978-3-319-19647-3_5",
language = "English (US)",
isbn = "9783319196466",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "45--51",
editor = "Chee Yap and Jianxin Wang",
booktitle = "Frontiers in Algorithmics - 9th International Workshop, FAW 2015, Proceedings",
address = "Germany",
}