A lower bound for approximating the Grundy number

Abstract : The grundy numbering of a graph is the maximum number of colors used by on-line first-fit coloring, under the worst order of arrival of vertices. The grundy numbering problem is to find this ordering. We prove that there is a constant c>1 so that approximating the grundy numbering problem within c is not possible, unless NP ⊆ RP
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.7--21
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966515
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 16:59:36
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:57:17

Fichier

dm090102.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966515, version 1

Collections

Citation

Guy Kortsarz. A lower bound for approximating the Grundy number. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.7--21. 〈hal-00966515〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

264