G-2016-111
Online algorithms for the maximum k-colorable subgraph problem
, et référence BibTeX
Le problème de la détermination du plus grand sous-graphe \(k\)
-colorable (\(k\)
-MCSP)
consiste à colorer autant de sommets que possible avec au plus \(k\)
couleurs, de telle
sorte que les sommets adjacents n'aient pas la même couleur. Nous considérons des
algorithmes en ligne (online) pour ce problème \(\mathcal{NP}\)
-dur, et nous donnons des bornes sur
leur ratio de compétitivité. Nous considérons ensuite une famille \(\cal{A}\)
d'algorithmes
de coloration séquentielle en ligne, et nous déterminons les plus petits graphes pour
lesquels aucun algorithme de la famille \(\cal{A}\)
n'est capable de générer une solution
optimale au problème \(k\)
-MCSP. Nous comparons ensuite les performances de
plusieurs algorithmes en ligne de coloration séquentielle, en utilisant les graphes de la
banque de données DIMACS. Finalement, nous considérons le cas où les sommets
colorés d'une certaine étape peuvent recevoir une nouvelle couleur plus tard, pour autant
qu'ils demeurent colorés.
Paru en novembre 2016 , 23 pages