{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:58Z","timestamp":1759637878858},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,9,13]],"date-time":"2012-09-13T00:00:00Z","timestamp":1347494400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00453-012-9688-5","type":"journal-article","created":{"date-parts":[[2012,9,12]],"date-time":"2012-09-12T17:14:07Z","timestamp":1347470047000},"page":"626-642","source":"Crossref","is-referenced-by-count":3,"title":["Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks"],"prefix":"10.1007","volume":"68","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,9,13]]},"reference":[{"key":"9688_CR1","series-title":"Cambridge Mathematical Library","volume-title":"Algebraic Graph Theory","author":"N. Biggs","year":"1993","unstructured":"Biggs, N.: Algebraic Graph Theory, 2nd\u00a0edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1993)","edition":"2"},{"issue":"2","key":"9688_CR2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02260499","volume":"35","author":"G. Tinhofer","year":"1985","unstructured":"Tinhofer, G., Schreck, H.: Computing the characteristic polynomial of a tree. Computing 35(2), 113\u2013125 (1985)","journal-title":"Computing"},{"issue":"2,3","key":"9688_CR3","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0304-3975(85)90049-0","volume":"36","author":"W. Keller-Gehrig","year":"1985","unstructured":"Keller-Gehrig, W.: Fast algorithms for the characteristic polynomial. Theor. Comput. Sci. 36(2,3), 309\u2013317 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9688_CR4","series-title":"Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol.\u00a0315. Springer, Berlin (1997)"},{"issue":"3","key":"9688_CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9688_CR6","doi-asserted-by":"crossref","first-page":"34","DOI":"10.13001\/1081-3810.1002","volume":"1","author":"G.H. Fricke","year":"1996","unstructured":"Fricke, G.H., Hedetniemi, S., Jacobs, D.P., Trevisan, V.: Reducing the adjacency matrix of a tree. Electron. J. Linear Algebra 1, 34\u201343 (1996)","journal-title":"Electron. J. Linear Algebra"},{"issue":"4","key":"9688_CR7","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/BF01169021","volume":"3","author":"B. Mohar","year":"1989","unstructured":"Mohar, B.: Computing the characteristic polynomial of a tree. J. Math. Chem. 3(4), 403\u2013406 (1989)","journal-title":"J. Math. Chem."},{"key":"9688_CR8","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing 7, 281\u2013292 (1971)","journal-title":"Computing"},{"issue":"3","key":"9688_CR9","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M. F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"key":"9688_CR10","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discrete Methods 8, 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9688_CR11","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9688_CR12","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108(1\u20132), 23\u201352 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"3\u20134","key":"9688_CR13","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"J.A. Makowsky","year":"2008","unstructured":"Makowsky, J.A.: From a zoo to a zoology: Towards a general theory of graph plynomials. Theory Comput. Syst. 43(3\u20134), 542\u2013562 (2008)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9688_CR14","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9688-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9688-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9688-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9688-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,13]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["9688"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9688-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,13]]}}}