Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
From MaRDI portal
Recommendations
Cites work
- H-coloring dichotomy revisited
- A new proof of the \(H\)-coloring dichotomy
- Applications of product colouring
- Bi‐arc graphs and the complexity of list homomorphisms
- Cardinal multiplication of structures with a reflexive relation
- Complexity of Finding Embeddings in a k-Tree
- Counterexamples to Hedetniemi's conjecture
- Deleting vertices to graphs of bounded genus
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- Exact algorithms for graph homomorphisms
- Families of strongly projective graphs
- Graph minors. III. Planar tree-width
- Graph Theory and Probability
- Handbook of product graphs
- Hedetniemi's conjecture---a survey
- House of Graphs: a database of interesting graphs
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- scientific article; zbMATH DE number 1775538 (Why is no real title available?)
- scientific article; zbMATH DE number 3445294 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Known algorithms on graphs of bounded treewidth are probably optimal
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- Lower bounds based on the exponential time hypothesis
- New plain-exponential time classes for graph homomorphism
- Nonserial dynamic programming
- Note on projective graphs
- On Cartesian skeletons of graphs
- On the complexity of k-SAT
- On the complexity of H-coloring
- Parameterized algorithms
- PRIMITIVE AND IMPRIMITIVE GRAPHS
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- S-functions for graphs
- Set partitioning via inclusion-exclusion
- Strongly Projective Graphs
- The Categorical Product of Graphs
- The core of a graph
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- The Kronecker Product of Graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tight lower bounds on graph embedding problems
- Which problems have strongly exponential complexity?
Cited in
(29)- Exact algorithms for graph homomorphisms
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- New Plain-Exponential Time Classes for Graph Homomorphism
- Lower bounds for the graph homomorphism problem
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
- scientific article; zbMATH DE number 932194 (Why is no real title available?)
- The Complexity of Homomorphism Indistinguishability
- Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Fundamentals of Computation Theory
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- List homomorphism: beyond the known boundaries
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- New perspectives on semiring applications to dynamic programming
- Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
- Fundamental problems on bounded-treewidth graphs: the real source of hardness
- A tight Monte-Carlo algorithm for Steiner tree parameterized by clique-width
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
- Towards exact structural thresholds for parameterized complexity
- Structural parameterizations for two bounded degree problems revisited
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- \(C_{2k+1}\)-coloring of bounded-diameter graphs
- List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
- Hitting meets packing: how hard can it be?
- Generalized graph packing problems parameterized by treewidth
- Tight bounds for some classical problems parameterized by cutwidth
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
This page was built for publication: Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5858645)
