MINIMUM GRAPH COLORING problem

Материал из WEGA
Версия от 14:35, 2 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''MINIMUM GRAPH COLORING problem''' --- задача о минимальной раскраске графа. The '''MINIMUM GRAPH COLORING problem''' (or ''' MGC…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

MINIMUM GRAPH COLORING problem --- задача о минимальной раскраске графа.

The MINIMUM GRAPH COLORING problem (or MGCP) consists in finding a coloring with the smallest number of colors. This problem is known to be NP-hard, approximable within factor [math]\displaystyle{ {\mathcal O}(|V|(\log \log |V|)^{2}/(\log |V|)^{3}) }[/math] and not approximable within factor [math]\displaystyle{ |V|^{1-\epsilon} }[/math] for any [math]\displaystyle{ \epsilon \gt 0 }[/math].