Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks

DOI10.1007/978-3-642-04128-0_2MaRDI QIDQ3639231zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_2

zbMATH Keywords

bounded tree-widthcharacteristic polynomialcounting independent setscounting matchingsefficient algorithms

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient computation of the characteristic polynomial of a tree and related tasks
• Computing the characteristic polynomial of a tree
• scientific article; zbMATH DE number 2235064
• scientific article; zbMATH DE number 1472121
• Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

Cited in

(13)

• Computing the characteristic polynomial of a tree
• Incremental and Efficient Computation of Families of Component Trees
• Efficient computation of the characteristic polynomial of a threshold graph
• Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width
• Computing the Euler characteristic and related additive functionals of digital objects from their bintree representation
• scientific article; zbMATH DE number 1472121 (Why is no real title available?)
• Efficient Schemes for Computing α-tree Representations
• Efficient computation of the characteristic polynomial of a threshold graph
• Computationally tractable approximate and smoothed Polya trees
• Efficient computation of the characteristic polynomial of a tree and related tasks
• scientific article; zbMATH DE number 2235064 (Why is no real title available?)
• Locating the eigenvalues of trees
• Fast evaluation of interlace polynomials on graphs of bounded treewidth

This page was built for publication: Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3639231)