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

Книга

Метод "критического" класса графов

Саарбрюкен: LAP LAMBERT Academic Publishing, 2010.

В книге рассматривается проблема определения границы между полиномиальной разрешимостью и NP-полнотой для классических графовых задач в решетке замкнутых относительно удаления вершин классов обыкновенных графов (решетке наследственных классов). Изучение данной границы ведется на основе метода критического класса графов поиска наследственных классов, играющих особую роль при решении упомянутой задачи демаркации. Исследуются два типа таких разделителей граничные и минимальные сложные классы графов, один из которых (минимальные сложные классы) был введен в рассмотрение автором.

В монографии представлены результаты автора по структуре граничных классов для ряда задач на графах. Например, показывается, что для обеих задач о 3-раскраске (вершинного и реберного вариантов) множество граничных классов континуально. В этой книге впервые предъявлены конкретные примеры минимальных сложных классов (ранее не было известно, существуют ли они вообще). С другой стороны, выделяется тип задач, для которых таких не существует. Данная книга предназначена для студентов, аспирантов и научных работников, занимающихся дискретной математикой.

Метод "критического" класса графов