Record Details

Fragmented coloring of proper interval and split graphs

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Fragmented coloring of proper interval and split graphs
 
Creator DIWAN, A
PAL, S
RANADE, A
 
Subject LIGHT-TRAILS
Proper interval graph
Split graph
Fragmented coloring
 
Description We study the fragmented coloring problem which is a generalization of the vertex coloring problem. A (lambda, C)-fragmented coloring of a graph G is an assignment of a color from {0, ..., lambda - 1} to each vertex of G such that every connected component in the graph induced by vertices of a single color has at most C vertices. For proper interval graphs, we give linear time and nearly linear time algorithms for the problems of minimizing lambda given C, and minimizing C given lambda. We also consider versions in which each vertex has a weight, and the sum of the weights in each induced connected component must be at most C. We give nearly linear time algorithms for the splittable weighted version and a 2-approximation for the non-splittable weighted version, all on proper interval graphs. We also prove that even the unweighted version is NP-hard for split graphs. (C) 2015 Elsevier B.V. All rights reserved.
 
Publisher ELSEVIER SCIENCE BV
 
Date 2016-01-14T13:36:57Z
2016-01-14T13:36:57Z
2015
 
Type Article
 
Identifier DISCRETE APPLIED MATHEMATICS, 193,110-118
0166-218X
1872-6771
http://dx.doi.org/10.1016/j.dam.2015.04.014
http://dspace.library.iitb.ac.in/jspui/handle/100/17632
 
Language en