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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Xiao ZHOU, Takao NISHIZEKI, "Graph Coloring Algorithms" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 407-417, March 2000, doi: .
Abstract: Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_407/_p
Copiar
@ARTICLE{e83-d_3_407,
author={Xiao ZHOU, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Graph Coloring Algorithms},
year={2000},
volume={E83-D},
number={3},
pages={407-417},
abstract={Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.},
keywords={},
doi={},
ISSN={},
month={March},}
Copiar
TY - JOUR
TI - Graph Coloring Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 407
EP - 417
AU - Xiao ZHOU
AU - Takao NISHIZEKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.
ER -