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 1719, 2016, Proceedings. Lecture Notes in Computer Science, 9843 . Springer, Switzerland, pp. 281292. ISBN 9783319445427
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 kMHV) problem asks to color the remaining vertices such that the number of happy vertices is maximized. The Maximum Happy Edges (also called kMHE) problem asks to color the remaining vertices such that the number of happy edges is maximized. For arbitrary graphs, kMHV and kMHE are NPHard 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: 



Item Type:  Book Section  
Uncontrolled Keywords:  Happy vertex, Happy edge, Graph coloring, Coloring trees  
Subjects:  Computer science > Big Data Analytics  
Divisions:  Department of Computer Science & Engineering  
Depositing User:  Team Library  
Date Deposited:  15 Sep 2016 09:40  
Last Modified:  20 Sep 2017 08:58  
URI:  http://raiith.iith.ac.in/id/eprint/2763  
Publisher URL:  https://doi.org/10.1007/9783319445434_22  
Related URLs: 
Actions (login required)
View Item 
Statistics for this ePrint Item 