Geodesic
On new algorithmic techniques for the weighted vertex coloring problem
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 4, pp. 442-448.

Voir la notice de l'article provenant de la source Math-Net.Ru

The classical NP-hard weighted vertex coloring problem consists in minimizing the number of colors in colorings of vertices of a given graph so that, for each vertex, the number of its colors equals a given weight of the vertex and adjacent vertices receive distinct colors. The weighted chromatic number is the smallest number of colors in these colorings. There are several polynomial-time algorithmic techniques for designing efficient algorithms for the weighted vertex coloring problem. For example, standard techniques of this kind are the modular graph decomposition and the graph decomposition by separating cliques. This article proposes new polynomial-time methods for graph reduction in the form of removing redundant vertices and recomputing weights of the remaining vertices so that the weighted chromatic number changes in a controlled manner. We also present a method of reducing the weighted vertex coloring problem to its unweighted version and its application. This paper contributes to the algorithmic graph theory.
Keywords: weighted vertex coloring problem, computational complexity.
Mots-clés : efficient algorithm 
@article{SVMO_2020_22_4_a3,
     author = {O. O. Razvenskaya},
     title = {On new algorithmic techniques for the weighted vertex coloring problem},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {442--448},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2020_22_4_a3/}
}
TY  - JOUR
AU  - O. O. Razvenskaya
TI  - On new algorithmic techniques for the weighted vertex coloring problem
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2020
SP  - 442
EP  - 448
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2020_22_4_a3/
LA  - ru
ID  - SVMO_2020_22_4_a3
ER  - 
%0 Journal Article
%A O. O. Razvenskaya
%T On new algorithmic techniques for the weighted vertex coloring problem
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2020
%P 442-448
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2020_22_4_a3/
%G ru
%F SVMO_2020_22_4_a3
O. O. Razvenskaya. On new algorithmic techniques for the weighted vertex coloring problem. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 4, pp. 442-448. http://geodesic.mathdoc.fr/item/SVMO_2020_22_4_a3/

[1] T. Gallai, “Transitiv orientierbare graphen”, Acta Mathematica Academiae Scientiarum Hungaricae, 18 (1967), 25–66 | DOI | MR | Zbl

[2] A. Cournier, M. Habib., “A new linear algorithm for modular decomposition”, Discrete Mathematics, 787 (1994), 68–84 | MR | Zbl

[3] R. Tarjan, “Decomposition by clique separators”, Discrete Mathematics, 55 (1985), 221–232 | DOI | MR | Zbl

[4] E. Edmonds, “Paths, trees, and flowers”, Canadian Journal of Mathematics, 17 (1965), 449–467 | DOI | MR | Zbl