Sobre a complexidade de coloração mista - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Sobre a complexidade de coloração mista

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.
Fichier principal
Vignette du fichier
artigo_ERPO.pdf (366.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00531712 , version 1 (03-11-2010)

Identifiants

  • HAL Id : inria-00531712 , version 1

Citer

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. ⟨inria-00531712⟩
167 Consultations
38 Téléchargements

Partager

Gmail Facebook X LinkedIn More