Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.43
URN: urn:nbn:de:0030-drops-55703
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5570/
Barbero, Florian ; Gutin, Gregory ; Jones, Mark ; Sheng, Bin
Parameterized and Approximation Algorithms for the Load Coloring Problem
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{barbero_et_al:LIPIcs:2015:5570,
author = {Florian Barbero and Gregory Gutin and Mark Jones and Bin Sheng},
title = {{Parameterized and Approximation Algorithms for the Load Coloring Problem}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {43--54},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5570},
URN = {urn:nbn:de:0030-drops-55703},
doi = {10.4230/LIPIcs.IPEC.2015.43},
annote = {Keywords: Load Coloring, fixed-parameter tractability, kernelization}
}
| Keywords: | Load Coloring, fixed-parameter tractability, kernelization | |
| Seminar: | 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 19.11.2015 |
