Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6892713 | Computers & Operations Research | 2018 | 16 Pages |
Abstract
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 NP-hard problem, and give bounds on their competitive ratio. We then consider a large family A of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Alain Hertz, Romain Montagné, François Gagnon,