Обложка Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации
Id: 103864

Полиэдральные графы и сложность в комбинаторной оптимизации

1995. 126 с. ISBN 5-230-20441-9. Букинист. Состояние: 4+. Есть погашенная библиотечная печать.
  • Твердый переплет
Аннотация

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

Книга представляет интерес для студентов, аспирантов, научных работников, специализирующихся в области вычислительной математики.

Обращаем Ваше внимание, что книги с пометкой "Предварительный заказ!" невозможно купить сразу. Если такие книги содержатся в Вашем заказе, их цена и стоимость доставки не учитываются в общей стоимости заказа. В течение 1-3 дней по электронной почте или СМС мы уточним наличие этих книг или отсутствие возможности их приобретения и сообщим окончательную стоимость заказа.

Оглавление

. наук Ю.А. Жура-иза сложных систем

е графы и сложность. ун-т. --- Ярославль,

зафов многогранни-гимизации, которые Основное внимание эафов, которая слу-лгоритмов из широких комбинаторных гальна по размерно-юненциальна --- для

спирантов, научных числительной мате-

: Российского фонда 17).

Предисловие 4

Глава 1. Введение

1.1. Задачи и алгоритмы комбинаторной оптимизации 7

1.2. Элементы теории выпуклых многогранников 15

Глава 2. Алгоритмы, использующие линейные сравнения

2.1. Унифицированная постановка задач комбинаторной оптимизации 26

2.2. Многогранники задач. Конусное разбиение 30

2.3. Линейные разделяющие деревья 32

2.4. Алгоритмы прямого типа 38

Глава 3. Алгоритмы и многогранники конкретных задач

3.1. Предварительные замечания 44

3.2. Задачи сортировки, перестановочные многогранники 45

3.3. Матроиды и "жадный" алгоритм 62

3.4. Задача о кратчайшем пути 69

3.5. Задачи о паросочетаниях 74

3.6. Задача коммивояжера 77

3.7. Другие труднорешаемые задачи 88

Глава 4. Многогранники с высокой плотностью графа и полиномиальная разрешимость задач

4.1. Об одной гипотезе Д. Гейла 105

4.2. К вопросу о полиномиальной разрешимости задач 106

4.3. Специальные многогранники, связанные с задачей "трехмерное сочетание" 109

4.4. Специальные многогранники с полным описанием

вершин 111

Литература 120