Grundy number on P4-classes

Julio Araujo 1 Claudia Linhares Sales 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this article, we define a new class of graphs, the fat-extended P4 -laden graphs, and we show a polynomial time algorithm to determine the Grundy number of the graphs in this class. This result implies that the Grundy number can be found in polynomial time for any graph of the following classes: P4 -reducible, extended P4 -reducible, P4 -sparse, extended P4 -sparse, P4 -extendible, P4 -lite, P4 -tidy, P4 -laden and extended P4 -laden, which are all strictly contained in the fat-extended P4 - laden class.
Type de document :
Communication dans un congrès
LAGOS'09 – V Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. Elsevier, 35, pp.21-27, 2009, Electronic Notes in Discrete Mathematics. <10.1016/j.endm.2009.11.005>
Liste complète des métadonnées


https://hal.inria.fr/inria-00531691
Contributeur : Julio Araujo <>
Soumis le : jeudi 4 novembre 2010 - 15:02:58
Dernière modification le : mardi 7 décembre 2010 - 10:51:21
Document(s) archivé(s) le : samedi 5 février 2011 - 02:28:11

Fichier

grundy_p4-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julio Araujo, Claudia Linhares Sales. Grundy number on P4-classes. LAGOS'09 – V Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. Elsevier, 35, pp.21-27, 2009, Electronic Notes in Discrete Mathematics. <10.1016/j.endm.2009.11.005>. <inria-00531691>

Partager

Métriques

Consultations de
la notice

265

Téléchargements du document

136