Радиораскраска в планарных графах: различия между версиями

Радиораскраска в планарных графах (посмотреть исходный код)

Нет изменений в размере , 12 апреля 2016

м

4446

правок

Версия от 13:45, 12 апреля 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 13:45, 12 апреля 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) Следующая правка →
Строка 65:		Строка 65:


	В [8] и [7] было доказано, что задача нахождения минимального диапазона для радиораскраски является NP-полной даже для графов диаметра 2. При редукции активно используются непланарные графы. В [11] было доказано, что задача раскраски квадрата графа общего вида является NP-полной.		В [8] и [7] было доказано, что задача нахождения минимального диапазона для радиораскраски является NP-полной даже для графов диаметра 2. При редукции активно используются непланарные графы. В [12] было доказано, что задача раскраски квадрата графа общего вида является NP-полной.