Analysis of the efficiency of graph coloring algorithms

Marek Kubale. "Analysis of the efficiency of graph coloring algorithms." Mathematica Applicanda 10.19 (1982): null. <http://eudml.org/doc/292823>.

@article{MarekKubale1982,
abstract = {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.},
author = {Marek Kubale},
journal = {Mathematica Applicanda},
keywords = {Computational complexity and efficiency of algorithms; Coloring of graphs and hypergraphs; Graph theory},
language = {eng},
number = {19},
pages = {null},
title = {Analysis of the efficiency of graph coloring algorithms},
url = {http://eudml.org/doc/292823},
volume = {10},
year = {1982},
}

TY - JOUR
AU - Marek Kubale
TI - Analysis of the efficiency of graph coloring algorithms
JO - Mathematica Applicanda
PY - 1982
VL - 10
IS - 19
SP - null
AB - 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.
LA - eng
KW - Computational complexity and efficiency of algorithms; Coloring of graphs and hypergraphs; Graph theory
UR - http://eudml.org/doc/292823
ER -