Efficient computation of the characteristic polynomial of a tree and related tasks
type: Item
instance of: scholarly article
title: Efficient computation of the characteristic polynomial of a tree and related tasks
zbMATH Open document ID: 1360.05083
published in: Algorithmica
publication date: 2017-05-17T00:00:00Z
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6718307
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: counting matchings
zbMATH Keywords: counting independent sets
zbMATH Keywords: bounded tree-width
zbMATH Keywords: efficient algorithms
author: Martin Fürer
MaRDI profile type: Publication
full work available at URL: s00453-012-9688-5
OpenAlex ID: W2059350284
cites work: Computing the characteristic polynomial of a tree
cites work: Fast algorithms for the characteristic polynomial
cites work: Q4331740
cites work: Matrix multiplication via arithmetic progressions
cites work: Reducing the adjacency matrix of a tree
cites work: Fast multiplication of large numbers
cites work: Faster Integer Multiplication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: From a zoo to a zoology: Towards a general theory of graph polynomials
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
DOI: 10.1007/S00453-012-9688-5
description: scientific article; zbMATH DE number 6718307