• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

On the complexity of path problems in properly colored directed graphs

Journal of Combinatorial Optimization. 2012. Vol. 24. No. 4. P. 459-467.
Granata D., Behdani B., Pardalos P. M.

Мы описываем класс  сложности нескольких проблем по поиску траектории  в хроматическом  направленном графе. Хроматический граф  определяется как граф G, множество вершин которого разбивается на X(G) стабильные множества, где  X(G) обозначает  хроматическое число G. Мы показываем, что нахождение простой траектории, которая соответствует всем хромам в хроматическом направленном графе, NP – сложное, так же как и задачи по поиску самой короткой и самой длинной траектории между  двумя определенными точками пересечения.