Parameterized algorithms for the happy set problem
DOI10.1016/j.dam.2021.07.005zbMath1473.05218OpenAlexW4206830864MaRDI QIDQ5919103
Tesshu Hanaka, Guo-Hui Lin, Eiji Miyano, Ippei Terabaru, Yuichi Asahiro, Hiroshi Eto
Publication date: 30 September 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2021.07.005
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A fast branching algorithm for cluster vertex deletion
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Algorithmic aspects of homophyly of networks
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Clustering and domination in perfect graphs
- Modular decomposition and transitive orientation
- Treewidth. Computations and approximations
- Complexity of finding dense subgraphs
- Finding happiness: an analysis of the maximum happy vertices problem
- On structural parameterizations of happy coloring, empire coloring and boxicity
- On the parameterized complexity of happy vertex coloring
- The parameterized complexity of happy colorings
- Improved approximation algorithms for the maximum happy vertices and edges problems
- Algorithmic meta-theorems for restrictions of treewidth
- Upper bounds to the clique width of graphs
- On happy colorings, cuts, and structural parameterizations
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- Approximating clique-width and branch-width
- Complexity and approximability of the happy set problem
- Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
- Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Linear FPT reductions and computational lower bounds
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Exact and Approximation Algorithms for Densest k-Subgraph
- Approximating rank-width and clique-width quickly
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Parameterized algorithms for the happy set problem
- Finding Branch-Decompositions and Rank-Decompositions
This page was built for publication: Parameterized algorithms for the happy set problem
