Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems

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

Mathematics Subject Classification ID

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