Parameterized complexity of happy coloring problems
From MaRDI portal
Publication:2192381
DOI10.1016/j.tcs.2020.06.002zbMath1460.68046OpenAlexW3037126423MaRDI QIDQ2192381
Juho Lauri, Subrahmanyam Kalyanasundaram, Akanksha Agrawal, I. Vinod Reddy, N. R. Aravind, Anjeneya Swami Kare, Neeldhara Misra
Publication date: 17 August 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.06.002
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)
Related Items
Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithmic aspects of homophyly of networks
- Exact exponential algorithms.
- Quadratic kernelization for convex recoloring of trees
- On the parameterized complexity of multiple-interval graph problems
- Treewidth. Computations and approximations
- On the parameterized complexity of happy vertex coloring
- The parameterized complexity of happy colorings
- Algorithmic meta-theorems for restrictions of treewidth
- On happy colorings, cuts, and structural parameterizations
- An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
- Set Partitioning via Inclusion-Exclusion
- Approximation Algorithms for Graph Homomorphism Problems
- On the multiway cut polyhedron
- Scaling Algorithms for Weighted Matching in General Graphs
- Kernelization
- Parameterized Algorithms
- Transitiv orientierbare Graphen
- Lower bounds for the happy coloring problems
