Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
From MaRDI portal
Publication:2819511
DOI10.1007/978-3-319-44543-4_22zbMath1454.68092OpenAlexW2531766656MaRDI QIDQ2819511
Anjeneya Swami Kare, Subrahmanyam Kalyanasundaram, N. R. Aravind
Publication date: 29 September 2016
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-44543-4_22
Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
A simple and effective algorithm for the maximum happy vertices problem ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ Finding happiness: an analysis of the maximum happy vertices problem ⋮ Complexity and approximability of the happy set problem ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Parameterized complexity of happy coloring problems ⋮ Parameterized algorithms for the happy set problem ⋮ Graph classes and approximability of the happy set problem ⋮ Tackling the maximum happy vertices problem in large networks ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ Lower bounds for the happy coloring problems
Cites Work
- Unnamed Item
- Algorithmic aspects of homophyly of networks
- Graph minors. X: Obstructions to tree-decomposition
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
- Approximation Algorithms for Graph Homomorphism Problems
- On the multiway cut polyhedron
- Network Flow and Testing Graph Connectivity
- Multi-Multiway Cut Problem on Graphs of Bounded Branch Width
This page was built for publication: Linear Time Algorithms for Happy Vertex Coloring Problems for Trees
