Linear Time Algorithms for Happy Vertex Coloring Problems for Trees

Aravind, N R and Kalyanasundaram, Subrahmanyam and Kare, A S (2016) Linear Time Algorithms for Happy Vertex Coloring Problems for Trees. In: Combinatorial Algorithms: 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings. Lecture Notes in Computer Science, 9843 . Springer, Switzerland, pp. 281-292. ISBN 978-3-319-44542-7

Text
aravind2016.pdf - Published Version
Restricted to Registered users only until 14 September 2018.
Download (212kB) | Request a copy

Abstract

Given an undirected graph G=(V,E) with |V|=n and a vertex coloring, a vertex v is happy if v and all its neighbors have the same color. An edge is happy if its end vertices have the same color. Given a partial coloring of the vertices of the graph using k colors, the Maximum Happy Vertices (also called k-MHV) problem asks to color the remaining vertices such that the number of happy vertices is maximized. The Maximum Happy Edges (also called k-MHE) problem asks to color the remaining vertices such that the number of happy edges is maximized. For arbitrary graphs, k-MHV and k-MHE are NP-Hard for k≥3. In this paper we study these problems for trees. For a fixed k we present linear time algorithms for both the problems. In general, for any k the proposed algorithms take O(nklogk) and O(nk) time respectively.

[error in script]

IITH Creators: