DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2015.43

Parameterized and Approximation Algorithms for the Load Coloring Problem

Authors: Florian Barbero, Gregory Gutin, Mark Jones, and Bin Sheng

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

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.

Cite as

Florian Barbero, Gregory Gutin, Mark Jones, and Bin Sheng. Parameterized and Approximation Algorithms for the Load Coloring Problem. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 43-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barbero_et_al:LIPIcs.IPEC.2015.43,
  author =	{Barbero, Florian and Gutin, Gregory and Jones, Mark and Sheng, Bin},
  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 =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.43},
  URN =		{urn:nbn:de:0030-drops-55703},
  doi =		{10.4230/LIPIcs.IPEC.2015.43},
  annote =	{Keywords: Load Coloring, fixed-parameter tractability, kernelization}
}

Search Results

Documents authored by Sheng, Bin

Parameterized and Approximation Algorithms for the Load Coloring Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message