@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",

}