Back

G-2016-111

Online algorithms for the maximum k-colorable subgraph problem

, , and

BibTeX reference

The maximum \(k\)-colorable subgraph problem (\(k\)-MCSP) is to color as many vertices as possible with at most \(k\) colors, such that no two adjacent vertices share the same color. We consider online algorithms for this \(\mathcal{NP}\)-hard problem, and give bounds on their competitive ratio. We then consider a large family \(\cal{A}\) of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in \(\cal{A}\) can produce an optimal solution to the \(k\)-MCSP. We then compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. We finally consider the case where vertices colored at an early stage can receive a new color later on, as long as they remain colored.

, 23 pages

Research Axes

Research application

Publication

, , and
Computers & Operations Research, 91, 209–224, 2018 BibTeX reference