Analysis of the efficiency of graph coloring algorithms

• Autorzy: Marek Kubale
• Języki publikacji: EN

Abstrakty

EN

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.

PL

.

Słowa kluczowe

EN

Computational complexity and efficiency of algorithms; Coloring of graphs and hypergraphs; Graph theory

• Wydawca: Polish Mathematical Society
• Czasopismo: Mathematica Applicanda
• Rocznik: 1982
• Tom: 10
• Numer: 19

Daty

wydano

1982

online

1982-02-01

Twórcy

autor

Marek Kubale

Identyfikatory

DOI

10.14708/ma.v10i19.1531