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

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

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

LAP Lambert Academic Publishing ( 2010-10-01 )

€ 49,00

Buy at the MoreBooks! Shop

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

Book Details:

ISBN-13:

978-3-8433-0142-8

ISBN-10:

3843301425

EAN:

9783843301428

Book language:

Russian

By (author) :

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

Number of pages:

88

Published on:

2010-10-01

Category:

Mathematics