Graph classes and approximability of the happy set problem
From MaRDI portal
Publication:2019476
DOI10.1007/978-3-030-58150-3_27OpenAlexW3081852812MaRDI QIDQ2019476
Yuichi Asahiro, Eiji Miyano, Ippei Terabaru, Hiroshi Eto, Tesshu Hanaka, Guo-Hui Lin
Publication date: 21 April 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_27
Cites Work
- Unnamed Item
- Unnamed Item
- PTAS for densest \(k\)-subgraph in interval graphs
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Algorithmic aspects of homophyly of networks
- Clustering and domination in perfect graphs
- 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
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Improved approximation algorithms for the maximum happy vertices and edges problems
- Exact algorithms for problems related to the densest \(k\)-set problem
- Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
- Detecting high log-densities
- Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Exact and Approximation Algorithms for Densest k-Subgraph
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Depth-First Search and Linear Graph Algorithms
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Parameterized algorithms for the happy set problem
- The dense \(k\)-subgraph problem
