Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

DOI10.1007/978-3-642-12200-2_6MaRDI QIDQ3557008zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 27 April 2010

Published in LATIN 2010: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-12200-2_6

zbMATH Keywords

bounded tree-widthchromatic polynomialcounting coloringsefficient algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4087683
• Efficient computation of the characteristic polynomial of a tree and related tasks
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks
• Evaluating a weighted graph polynomial for graphs of bounded tree-width

Cited in

(10)

• Evaluating a weighted graph polynomial for graphs of bounded tree-width
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• On the colored Tutte polynomial of a graph of bounded treewidth
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Efficient computation of the modular chromatic numbers of trees
• Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks
• scientific article; zbMATH DE number 140132 (Why is no real title available?)
• scientific article; zbMATH DE number 1409207 (Why is no real title available?)
• Efficient computation of the characteristic polynomial of a tree and related tasks
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

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