Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time

S. Kennedy C. Meagher Bruce Reed 1, 2
1 SOCS - School of Computer Science [Quebec]
2 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 : For any c>1, we describe a linear time algorithm for fractionally edge colouring simple graphs with maximum degree at least |V|/c.
Type de document :
Communication dans un congrès
European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009), 2009, Bordeaux, France. 34, pp.47―51, 2009, Electronic Notes on Discrete Mathematics. 〈10.1016/j.endm.2009.07.008〉
Liste complète des métadonnées
https://hal.inria.fr/hal-00795286
Contributeur : Alain Monteil <>
Soumis le : mercredi 27 février 2013 - 17:03:21
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04

Identifiants

Collections

UNICE | INRIA | I3S | UNIV-COTEDAZUR

Citation

S. Kennedy, C. Meagher, Bruce Reed. Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time. European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009), 2009, Bordeaux, France. 34, pp.47―51, 2009, Electronic Notes on Discrete Mathematics. 〈10.1016/j.endm.2009.07.008〉. 〈hal-00795286〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

165

Contact


archive-ouverte@inria.fr