Sobre a complexidade de coloração mista

Julio Araujo 1 Manoel Campêlo 2 Phablo Moura 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
Résumé : Grafos mistos são estruturas matemáticas que mesclam características de grafos direcionados e não-direcionados. Formalmente, um grafo misto pode ser definido por uma tripla GM = (V, A, E), onde V , A e E representam, respectivamente, um conjunto de vértices, de arcos e de arestas. Uma k-coloração mista de GM = (V, A, E) é função c : V → {0, . . . , k − 1} tal que c(u) < c(v), se (u, v) ∈ A, e c(u) = c(v), se [u, v] ∈ E. O problema de Coloração Mista consiste em determinar o número cromático misto de GM , denotado por χM (GM ), que é o menor inteiro k tal que GM admite uma k-coloração mista. Esse problema modela variações de problemas de escalonamento que consideram simultaneamente restrições de precedência e de compartilhamento de recursos. Neste trabalho, mostramos que Coloração Mista é N P -difícil para as classes dos grafos cordais, dos grafos linha de grafos bipartidos e dos grafos linha de grafos periplanares.
Type de document :
Communication dans un congrès
III Encontro Regional de Pesquisa Operacional do Nordeste (III ERPONE), Nov 2009, Fortaleza, Brazil. 2009
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00531712
Contributeur : Julio Araujo <>
Soumis le : mercredi 3 novembre 2010 - 15:38:48
Dernière modification le : jeudi 11 janvier 2018 - 16:50:01
Document(s) archivé(s) le : vendredi 4 février 2011 - 02:59:26

Fichier

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

Identifiants

  • HAL Id : inria-00531712, version 1

Collections

Citation

Julio Araujo, Manoel Campêlo, Phablo Moura. Sobre a complexidade de coloração mista. III Encontro Regional de Pesquisa Operacional do Nordeste (III ERPONE), Nov 2009, Fortaleza, Brazil. 2009. 〈inria-00531712〉

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

79