Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
From MaRDI portal
Publication:3196381
DOI10.1007/978-3-319-21398-9_13zbMath1386.68225MaRDI QIDQ3196381
Peng Zhang, Tao Jiang, Ang Sheng Li
Publication date: 29 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_13
90C35: Programming involving graphs or networks
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
68W25: Approximation algorithms
Related Items
Parameterized algorithms for the happy set problem, Lower bounds for the happy coloring problems, Finding happiness: an analysis of the maximum happy vertices problem, Improved approximation algorithms for the maximum happy vertices and edges problems, Graph classes and approximability of the happy set problem, Parameterized complexity of happy coloring problems, Approximation algorithms for vertex happiness, Complexity and approximability of the happy set problem, Linear Time Algorithms for Happy Vertex Coloring Problems for Trees, Approximation and Hardness Results for the Max k-Uncut Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Algorithmic aspects of homophyly of networks
- An improved approximation algorithm of MULTIWAY CUT.
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Approximation algorithms for classification problems with pairwise relationships
- Approximation Algorithms for Graph Homomorphism Problems
- The Complexity of Multiterminal Cuts
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Simplex partitioning via exponential clocks and the multiway cut problem