Farrell polynomials on graphs of bounded tree width

DOI10.1016/S0196-8858(02)00530-4zbMath1023.68070MaRDI QIDQ1398293

J. P. Mariño, Johann A. Makowsky

Publication date: 29 July 2003

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational complexitygenerating functionscombinatorial enumerationmonadic second-order logicdefinabilitygraph polynomialsFarrell polynomials

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the bivariate permanent polynomials of graphs, The parametrized complexity of knot polynomials, An algorithm for calculating the independence and vertex-cover polynomials of a graph, Algorithmic uses of the Feferman-Vaught theorem, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Counting truth assignments of formulas of bounded tree-width or clique-width, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Linear Recurrence Relations for Graph Polynomials, From a zoo to a zoology: Towards a general theory of graph polynomials

Cites Work

• The complexity of computing the permanent
• Matching theory
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• On a general class of graph polynomials
• An introduction to matching polynomials
• Mathematical foundations of computer science 1997. 22nd international symposium, MFCS '97, Bratislava, Slovakia, August 25--29, 1997. Proceedings
• Graph characterising polynomials
• Clique polynomials and independent set polynomials of graphs
• Problems in algebraic combinatorics
• New results for the Martin polynomial
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• The parametrized complexity of knot polynomials
• Linear time solvable optimization problems on graphs of bounded clique-width
• Dependence polynomials
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Le Polynôme De Martin D'un Graphe Eulerien
• Easy problems for tree-decomposable graphs
• The Complexity of Defining a Relation on a Finite Graph
• On the theory of the matching polynomial
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Tutte Polynomial for Coloured Graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item