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