A computational framework for the study of partition functions and graph polynomials

DOI10.1142/9789814449274_0012zbMATH Open1364.03055OpenAlexW4229671577MaRDI QIDQ5737993FDOQ5737993

Authors: Tomer Kotek, Johann A. Makowsky, E. Ravve 

Publication date: 31 May 2017

Published in: Proceedings of the 12th Asian Logic Conference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/9789814449274_0012

Recommendations

• Combinatorics and complexity of partition functions
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• The complexity of partition functions
• Some algorithmic applications of partition functions in combinatorics
• Automata, Languages and Programming

zbMATH Keywords

graph polynomialscomplexity of computationcounting problemspartition functionsmodels of computation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Cited In (8)

• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Title not available (Why is that?)
• Computing the partition function for graph homomorphisms
• Semantic equivalence of graph polynomials definable in second order logic
• A logician's view of graph polynomials
• Combinatorics and complexity of partition functions
• Title not available (Why is that?)
• On the complexity of generalized chromatic polynomials

This page was built for publication: A computational framework for the study of partition functions and graph polynomials

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