Improved approximation algorithms for the maximum happy vertices and edges problems

DOI10.1007/978-3-319-21398-9_13MaRDI QIDQ3196381zbMATH OpenOpenAlexFDO

Authors Peng Zhang, Tao Jiang, Angsheng 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)

Recommendations

• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation algorithms for vertex happiness
• Algorithmic aspects of homophyly of networks

Cites work

• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• Algorithmic aspects of homophyly of networks
• An improved approximation algorithm of MULTIWAY CUT.
• Approximation Algorithms for Graph Homomorphism Problems
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Networks, crowds and markets. Reasoning about a highly connected world.
• Simplex partitioning via exponential clocks and the multiway cut problem
• The Complexity of Multiterminal Cuts

Cited in

(16)

• Finding happiness: an analysis of the maximum happy vertices problem
• A simple and effective algorithm for the maximum happy vertices problem
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation and hardness results for the max \(k\)-uncut problem
• Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
• Tackling the maximum happy vertices problem in large networks
• The maximum happy induced subgraph problem: bounds and algorithms
• Parameterized algorithms for the happy set problem
• Complexity and approximability of the happy set problem
• Approximation Algorithms for Graph Homomorphism Problems
• Kernelization for maximum happy vertices problem
• Parameterized complexity of happy coloring problems
• Graph classes and approximability of the happy set problem
• Algorithmic aspects of homophyly of networks
• Maximizing happiness in graphs of bounded clique-width
• Approximation algorithms for vertex happiness

This page was built for publication: Improved approximation algorithms for the maximum happy vertices and edges problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196381)