TY - GEN
T1 - Efficient computation of the characteristic polynomial of a tree and related tasks
AU - Fürer, Martin
PY - 2009
Y1 - 2009
N2 - An O(n log2 n) algorithm is presented to compute the characteristic polynomial of a tree on n vertices improving on the previously best quadratic time. With the same running time, the algorithm can be generalized in two directions. The algoritm is a counting algorithm, and the same ideas can be used to count other objects. For example, one can count the number of independent sets of all possible sizes simultaneously with the same running time. These counting algorithms not only work for trees, but can be extended to arbitrary graphs of bounded tree-width.
AB - An O(n log2 n) algorithm is presented to compute the characteristic polynomial of a tree on n vertices improving on the previously best quadratic time. With the same running time, the algorithm can be generalized in two directions. The algoritm is a counting algorithm, and the same ideas can be used to count other objects. For example, one can count the number of independent sets of all possible sizes simultaneously with the same running time. These counting algorithms not only work for trees, but can be extended to arbitrary graphs of bounded tree-width.
UR - http://www.scopus.com/inward/record.url?scp=70350397063&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350397063&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04128-0_2
DO - 10.1007/978-3-642-04128-0_2
M3 - Conference contribution
AN - SCOPUS:70350397063
SN - 3642041272
SN - 9783642041273
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 11
EP - 22
BT - Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings
T2 - 17th Annual European Symposium on Algorithms, ESA 2009
Y2 - 7 September 2009 through 9 September 2009
ER -