Parameterized and approximation algorithms for the load coloring problem

DOI10.1007/S00453-016-0259-ZMaRDI QIDQ2408202zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yanyan Li

Publication date 10 October 2017

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1412.3023

zbMATH Keywords

approximation algorithmsFPTkernelsload coloringparameterized algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: Let $c,k$ be two positive integers and let $G=(V,E)$ be a graph. The $(c,k)$-Load Coloring Problem (denoted $(c,k)$-LCP) asks whether there is a $c$-coloring $varphi:Vightarrow[c]$ such that for every $iin[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,k)$-LCP 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 $cge2$, $(c,k)$-LCP is FPT and that the optimization version of $(c,k)$-LCP (where $k$ is to be maximized) has an approximation algorithm with a constant ratio for any fixed $cge2$.

Recommendations

• Parameterized and approximation algorithms for the load coloring problem
• Parameterized algorithms for load coloring problem
• On the minimum load coloring problem
• Approximation and Online Algorithms
• Coloring Graphs with Minimal Edge Load

Cites work

• (Meta) Kernelization
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• Fixed-parameter complexity of minimum profile problems
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 15366 (Why is no real title available?)
• Kernelization -- preprocessing with a guarantee
• On the minimum load coloring problem
• Parameterized algorithms
• Parameterized algorithms for load coloring problem
• Parameterized and approximation algorithms for the load coloring problem
• Recent developments in kernelization: a survey
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The linear arrangement problem parameterized above guaranteed value
• The ring of \(k\)-regular sequences. II.

Cited in

(12)

• Load balancing by graph coloring, an algorithm
• Reinforcement learning based tabu search for the minimum load coloring problem
• Parameterized algorithms for load coloring problem
• On the minimum load coloring problem
• Dealing with several parameterized problems by random methods
• Coloring Graphs with Minimal Edge Load
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Parameterized and approximation algorithms for the load coloring problem
• Approximation and Online Algorithms
• A general variable neighborhood search approach for the minimum load coloring problem
• On structural parameterizations of load coloring
• On structural parameterizations of load coloring

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Parameterized and approximation algorithms for the load coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408202)