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

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

Поиск пределов эффективной разрешимости в решетке наследственно замкнутых классов

LAP Lambert Academic Publishing ( 01.10.2010 )

€ 49,00

MoreBooks! sitesinden satın al

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

Kitap detayları:

ISBN-13:

978-3-8433-0142-8

ISBN-10:

3843301425

EAN:

9783843301428

Kitabın dili:

Russian

Yazar:

Дмитрий Малышев

Sayfa sayısı:

88

Yayın tarihi:

01.10.2010

Kategori:

Matematik