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

[img] 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:
IITH CreatorsORCiD
Aravind, N RUNSPECIFIED
Kalyanasundaram, SubrahmanyamUNSPECIFIED
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/978-3-319-44543-4_22
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2763 Statistics for this ePrint Item