scientific article; zbMATH DE number 7651213
From MaRDI portal
Publication:5874546
Cites work
- A c^k n 5-approximation algorithm for treewidth
- A complete complexity classification of the role assignment problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Bi‐arc graphs and the complexity of list homomorphisms
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Complexity of Finding Embeddings in a k-Tree
- Computing the chromatic number using graph decompositions via matrix rank
- Constraint satisfaction problems: complexity and algorithms
- 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
- Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Handbook of product graphs
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (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
- Mathematical Foundations of Computer Science 2005
- New plain-exponential time classes for graph homomorphism
- On the complexity of k-SAT
- On the complexity of H-coloring
- Parameterized algorithms
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Set partitioning via inclusion-exclusion
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- The complexity of first-order and monadic second-order logic revisited
- The complexity of the list homomorphism problem for graphs
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- 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
(23)- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- The parameterised complexity of list problems on graphs of bounded treewidth
- Bi‐arc graphs and the complexity of list homomorphisms
- Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Sparsification lower bounds for list \(H\)-coloring
- List homomorphism: beyond the known boundaries
- 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
- Sparsification lower bounds for list H-coloring
- The fine-grained complexity of graph homomorphism parameterized by clique-width
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
- Complexity of the list homomorphism problem in hereditary graph classes
- Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
- \(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
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874546)
