文章基本信息

标题：Parameterized and Approximation Algorithms for the Load Coloring Problem
本地全文：下载
作者：Florian Barbero ; Gregory Gutin ; Mark Jones 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：43
页码：43-54
DOI：10.4230/LIPIcs.IPEC.2015.43
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Let c, k be two positive integers. Given a graph G=(V,E), the c-Load Coloring problem asks whether there is a c-coloring varphi: V => [c] such that for every i in [c], there are at least k edges with both endvertices colored i. Gutin and Jones (IPL 2014) studied this problem with c=2. They showed 2-Load Coloring to be fixed-parameter tractable (FPT) with parameter k by obtaining a kernel with at most 7k vertices. In this paper, we extend the study to any fixed c by giving both a linear-vertex and a linear-edge kernel. In the particular case of c=2, we obtain a kernel with less than 4k vertices and less than 8k edges. These results imply that for any fixed c >= 2, c-Load Coloring is FPT and the optimization version of c-Load Coloring (where k is to be maximized) has an approximation algorithm with a constant ratio.
关键词：Load Coloring; fixed-parameter tractability; kernelization