Parameterized counting of partially injective homomorphisms
From MaRDI portal
Publication:2032353
DOI10.1007/s00453-021-00805-yOpenAlexW3138370239WikidataQ114229329 ScholiaQ114229329MaRDI QIDQ2032353
Publication date: 11 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-021-00805-y
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A dichotomy for real weighted Holant problems
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Combinatorics and complexity of partition functions
- The complexity of computing the permanent
- Holographic algorithms: from art to science
- The complexity of counting homomorphisms seen from the other side
- Counting induced subgraphs: a topological approach to \#W[1-hardness]
- Strong computational lower bounds via parameterized complexity
- An approximation trichotomy for Boolean \#CSP
- A note on the graph isomorphism counting problem
- Counting trees in a graph is \(\# \text{P}\)-complete
- Counting \(H-\)colorings of partial \(k-\)trees
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Computational complexity of counting problems on 3-regular planar graphs
- Parameterized counting of trees, forests and matroid bases
- Parametrized complexity theory.
- On tree width, bramble size, and expansion
- \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
- Homomorphisms of derivative graphs
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized counting problems
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- The statistics of dimers on a lattice
- Approximating the Permanent
- Holographic Algorithms
- The Complexity of Enumeration and Reliability Problems
- On the Structure of Polynomial Time Reducibility
- Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Counting Unlabelled Subtrees of a Tree is #P-complete
- The Parameterized Complexity of the k -Biclique Problem
- The Parameterized Complexity of Counting Problems
- Homomorphisms are a good basis for counting small subgraphs
- Size Bounds for Factorised Representations of Query Results
- Counting Answers to Existential Questions
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- Zeros of Holant problems: locations and algorithms
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Dimer problem in statistical mechanics-an exact result
- The complexity of satisfiability problems
- Parameterized Algorithms
- [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Computational Complexity
- On the complexity of \(k\)-SAT
