scientific article; zbMATH DE number 7376013
From MaRDI portal
Publication:5002765
DOI10.4230/LIPIcs.ICALP.2018.86zbMath1499.68282MaRDI QIDQ5002765
Publication date: 28 July 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (3)
Parameterized (Approximate) Defective Coloring ⋮ Unnamed Item ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Between treewidth and clique-width
- Model counting for CNF formulas of bounded modular treewidth
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Zero knowledge and the chromatic number
- Which problems have strongly exponential complexity?
- Algorithmic meta-theorems for restrictions of treewidth
- Edge dominating set and colorings on graphs with fixed clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- Parameterized Compilation Lower Bounds for Restricted CNF-Formulas
- Parameterized Algorithms for Modular-Width
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Intractability of Clique-Width Parameterizations
- Clique-Width is NP-Complete
- Faster Algorithms on Branch and Clique Decompositions
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
- Optimal dynamic program for r-domination problems over tree decompositions
- On Problems as Hard as CNF-SAT
- Tight Lower Bounds for the Complexity of Multicoloring
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication:
