Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00531712
Contributor : Julio Araujo <>
Submitted on : Wednesday, November 3, 2010 - 3:38:48 PM
Last modification on : Monday, October 12, 2020 - 10:30:18 AM
Long-term archiving on: : Friday, February 4, 2011 - 2:59:26 AM

File

artigo_ERPO.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00531712⟩

Share

Metrics

Record views

335

Files downloads

104