Efficient computation of the characteristic polynomial of a tree and related tasks

DOI10.1007/s00453-012-9688-5zbMath1360.05083OpenAlexW2059350284MaRDI QIDQ528854

Martin Fuerer

Publication date: 17 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9688-5

zbMATH Keywords

characteristic polynomialefficient algorithmsbounded tree-widthcounting independent setscounting matchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph polynomials (05C31) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

On the Hosoya index of a family of deterministic recursive trees ⋮ Efficient Computation of the Characteristic Polynomial of a Threshold Graph ⋮ Efficient computation of the characteristic polynomial of a threshold graph

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Computing the characteristic polynomial of a tree
• Fast algorithms for the characteristic polynomial
• Fast multiplication of large numbers
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Faster Integer Multiplication
• Complexity of Finding Embeddings in a k-Tree
• Reducing the adjacency matrix of a tree
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Efficient computation of the characteristic polynomial of a tree and related tasks