A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Graph Coloring Algorithms Algoritmos de coloração de gráficos

Xiao ZHOU, Takao NISHIZEKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

A coloração de gráficos é um problema fundamental, que frequentemente aparece em vários problemas de escalonamento, como o problema de transferência de arquivos em redes de computadores. Neste artigo, examinamos os avanços e resultados recentes sobre a coloração de bordas, o f-coloração, o [g,f]-coloração e o problema de coloração total para várias classes de gráficos, como gráficos bipartidos, gráficos paralelos em série, gráficos planares e gráficos com degeneração fixa, largura de árvore, gênero, arboricidade, índice unicíclico ou espessura. Em particular, revisamos vários limites superiores sobre o número mínimo de cores necessárias para colorir essas classes de grafos e apresentamos algoritmos sequenciais e paralelos eficientes para encontrar colorações de grafos com esses números de cores.

Publicação
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.407-417
Data de publicação
2000/03/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
INVITED SURVEY PAPER
Categoria
Algoritmos de gráfico

autores

Palavra-chave