Counting edge-injective homomorphisms and matchings on restricted graph classes
DOI10.1007/s00224-018-9893-yzbMath1429.68080OpenAlexW2898827567WikidataQ114230787 ScholiaQ114230787MaRDI QIDQ2321927
Holger Dell, Marc Roth, Radu Curticapean
Publication date: 27 August 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7008/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Holographic algorithms: from art to science
- Generalized model-checking over locally tree-decomposable classes
- The complexity of counting homomorphisms seen from the other side
- The strong perfect graph theorem
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Approximating the permanent of graphs with large factors
- Maximum cut on line and total graphs
- Forbidden induced subgraphs for line graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Disjoint triangles of a cubic line graph
- Complexity of generalized satisfiability counting problems
- Computational complexity of counting problems on 3-regular planar graphs
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Finding, Minimizing, and Counting Weighted Subgraphs
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Computational Complexity of Holant Problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
- Holographic Algorithms
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- The Parameterized Complexity of Counting Problems
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Homomorphisms are a good basis for counting small subgraphs
- Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- When is the evaluation of conjunctive queries tractable?
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Dimer problem in statistical mechanics-an exact result
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- On the power of parity polynomial time
This page was built for publication: Counting edge-injective homomorphisms and matchings on restricted graph classes
