Methods of classification and algorithms of graph coloring

V.A. Perepelitsa; I.V. Kozin; S.V. Kurapov

doi:10.15421/240816

Methods of classification and algorithms of graph coloring

V.A. Perepelitsa (Zaporizhzhia National University)
I.V. Kozin (Zaporizhzhia National University)
S.V. Kurapov (Zaporizhzhia National University)

Abstract

We study the connection between classifications on finite set and the problem of graph coloring. We consider the optimality criterion for classification of special type: h-classifications, which are built on the base of proximity measure. It is shown that the problem of finding the optimal h-classification can be reduced to the problem of coloring of non-adjacency graph vertices by the smallest possible number of colors. We consider algorithms of proper coloring of graph vertices.

Full Text:

PDF (Русский)

References

Aivazian S.A., Bukhshtaber V.M., Eniukov I.S., Meshalkin L.D. Applied Statistics: Classification and dimensionality reduction, 1989. (in Russian)

Kozin I.V. "Fragmentary algorithms in decision making support systems", Problems of appl. math. and math. model.: Coll. sci works, Dnipropetrovsk, 2005; pp. 131-137. (in Russian)

Kozin I.V., Kurapov S.V. "Algorithms of optimal classification", Visnyk Zaporiz. nat. un-tu, 2005; 1: pp. 25-29. (in Russian)

Kim J.O., Muller Ch.U., Klekka U.R. Factor, discriminant, and cluster analysis, 1989. (in Russian)

Kristofides N. Graph Theory. Algorithmic approach, 1978. (in Russian)

Sergienko I.V. Mathematical models and methods of discrete optimization problem solving, 1988. (in Russian)