scientific article; zbMATH DE number 7651213
From MaRDI portal
Publication:5874546
DOI10.4230/LIPIcs.ESA.2020.74MaRDI QIDQ5874546
Marta Piecyk, Paweł Rzążewski, Karolina Okrasa
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2006.11155
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (3)
List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- List H-coloring a graph by removing few vertices
- New plain-exponential time classes for graph homomorphism
- The complexity of the list homomorphism problem for graphs
- A complete complexity classification of the role assignment problem
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- On the complexity of H-coloring
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- List homomorphisms to reflexive graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Which problems have strongly exponential complexity?
- Constraint satisfaction problems: complexity and algorithms
- The complexity of first-order and monadic second-order logic revisited
- List homomorphisms and circular arc graphs
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Deleting vertices to graphs of bounded genus
- Computing the chromatic number using graph decompositions via matrix rank
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Exact algorithms for graph homomorphisms
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Set Partitioning via Inclusion-Exclusion
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Complexity of Finding Embeddings in a k-Tree
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- Tight Lower Bounds on Graph Embedding Problems
- Bi‐arc graphs and the complexity of list homomorphisms
- Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Mathematical Foundations of Computer Science 2005
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On the complexity of \(k\)-SAT
This page was built for publication:
