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

Статья

Boundary properties of graphs for algorithmic graph problems

Theoretical Computer Science. 2011. No. 412. P. 3545-3554.
Korpelainen N., Lozin V. V., Malyshev D., Tiskin A.

Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. В частности, мы выявляем два граничных класса для задачи о гамильтоновом цикле и доказываем, что при k>3 существует континуум граничных классов для задачи о вершинной k-раскраске.