Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems

DOI10.1007/978-3-319-21398-9_13zbMath1386.68225OpenAlexW3023272694MaRDI 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

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (10)

Finding happiness: an analysis of the maximum happy vertices problem ⋮ Complexity and approximability of the happy set problem ⋮ Parameterized complexity of happy coloring problems ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ Parameterized algorithms for the happy set problem ⋮ Graph classes and approximability of the happy set problem ⋮ Lower bounds for the happy coloring problems ⋮ Linear Time Algorithms for Happy Vertex Coloring Problems for Trees ⋮ Approximation algorithms for vertex happiness

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

This page was built for publication: Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems