On Counting Homomorphisms to Directed Acyclic Graphs

DOI10.1007/11786986_5MaRDI QIDQ3613747zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Dyer, Leslie Ann Goldberg, Mike Paterson

Publication date 12 March 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11786986_5

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1545676
• scientific article; zbMATH DE number 1445311
• Counting homomorphisms and partition functions
• Counting homomorphisms to trees modulo a prime
• Counting homomorphisms to trees modulo a prime

Cited in

(8)

• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Dichotomy theorems for homomorphism polynomials of graph classes
• The complexity of counting homomorphisms to cactus graphs modulo 2
• scientific article; zbMATH DE number 6691415 (Why is no real title available?)
• On counting homomorphisms to directed acyclic graphs
• Complexity and approximability of the cover polynomial
• Topological additive numbering of directed acyclic graphs
• Bounded degree nonnegative counting CSP

This page was built for publication: On Counting Homomorphisms to Directed Acyclic Graphs

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