Geodesic
Analysis of the efficiency of graph coloring algorithms
Mathematica Applicanda, Tome 10 (1982) no. 19, pp. 23-41.

Voir la notice de l'article provenant de la source Annales Societatis Mathematicae Polonae Series

This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.
DOI : 10.14708/ma.v10i19.1531
Classification : 68C25(05C15 68E10)
Mots-clés : Computational complexity and efficiency of algorithms, Coloring of graphs and hypergraphs, Graph theory 
@article{10_14708_ma_v10i19_1531,
     author = {Marek Kubale},
     title = {Analysis of the efficiency of graph coloring algorithms},
     journal = {Mathematica Applicanda},
     pages = { 23--41},
     publisher = {mathdoc},
     volume = {10},
     number = {19},
     year = {1982},
     doi = {10.14708/ma.v10i19.1531},
     language = {pl},
     url = {http://geodesic.mathdoc.fr/articles/10.14708/ma.v10i19.1531/}
}
TY  - JOUR
AU  - Marek Kubale
TI  - Analysis of the efficiency of graph coloring algorithms
JO  - Mathematica Applicanda
PY  - 1982
SP  -  23
EP  - 41
VL  - 10
IS  - 19
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14708/ma.v10i19.1531/
DO  - 10.14708/ma.v10i19.1531
LA  - pl
ID  - 10_14708_ma_v10i19_1531
ER  - 
%0 Journal Article
%A Marek Kubale
%T Analysis of the efficiency of graph coloring algorithms
%J Mathematica Applicanda
%D 1982
%P  23-41
%V 10
%N 19
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14708/ma.v10i19.1531/
%R 10.14708/ma.v10i19.1531
%G pl
%F 10_14708_ma_v10i19_1531
Marek Kubale. Analysis of the efficiency of graph coloring algorithms. Mathematica Applicanda, Tome 10 (1982) no. 19, pp.  23-41. doi : 10.14708/ma.v10i19.1531. http://geodesic.mathdoc.fr/articles/10.14708/ma.v10i19.1531/

Cité par Sources :