Пападимитриу Х., Стайглиц К. — Комбинаторная оптимизация. Алгоритмы и сложность. :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Пападимитриу Х., Стайглиц К. — Комбинаторная оптимизация. Алгоритмы и сложность.

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Комбинаторная оптимизация. Алгоритмы и сложность.

Авторы: Пападимитриу Х., Стайглиц К.

Язык:

Рубрика: Математика/Алгебра/Комбинаторика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1984

Количество страниц: 512

Добавлена в каталог: 10.03.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

$\Delta$ -замена      476
3-связность      470
d-гиперкуб      см. «Куб d-мерный»
j-перешеек      220
k-замена      15 468
M-цикл      303
n-мерное действительное векторное пространство      24
NP-полнота      325
NP-трудность      408
p-квантили      311
PSPACE      411
s-t-разрез      121
s-t-разрез, пропускная способность      121
s-t-связность      139 221
X-замена      473
X-замена выгодная      473
X-замена, окрестность      473
Алгол Упрощенный      27
Алгоритм $\varepsilon$ -приближенный      421
Алгоритм АЛЬФАБЕТА      152
Алгоритм асимптотически оптимальный      285
Алгоритм Блэнда      58
Алгоритм двухэтапный      63
Алгоритм Дейкстры      133
Алгоритм декомпозиции      104
Алгоритм дерева      426
Алгоритм для задачи МОД второй      286
Алгоритм для задачи о пересечении матроидов      307
Алгоритм ДОСТРОЙКА      147
Алгоритм ДП-I      432
Алгоритм ДП-II      434
Алгоритм ДП-III      435
Алгоритм ДП-IV      439
Алгоритм дробный двойственный для задачи ЦЛП      340
Алгоритм жадный для задачи ЛМВ      288
Алгоритм жадный для матроидов      291
Алгоритм Кристофидеса      429
Алгоритм локального поиска      467
Алгоритм НАЙТИПУТЬ      203
Алгоритм недопустимый относительно задачи      147
Алгоритм ПОИСК      199
Алгоритм построения взвешенного паросочетания      270
Алгоритм построения максимального потока      215
Алгоритм построения минимального остовного дерева      282
Алгоритм построения паросочетания в двудольном графе      229
Алгоритм построения паросочетания в произвольном графе      244
Алгоритм проверки удостоверения      359
Алгоритм прямо-двойственный      106 111
Алгоритм прямо-допустимый      145
Алгоритм псевдополиномиальный      197 401
Алгоритм рекурсивный      220
Алгоритм сильно полиномиальный      197
Алгоритм Флойда — Уоршелла      136
Алгоритм Форда — Фалкерсона      127
Алгоритм ЦИКЛ      143
Алгоритм эллипсоидов для задачи СЛН      182
Алгоритм эллипсоидов модифицированный      189
Алгоритм, допустимый относительно задачи      145
Алгоритмы      160
Алгоритмы вероятностные      413
Алгоритмы отсекающей плоскости      336
Алгоритмы отсекающей плоскости прямые целочисленные      350
Алгоритмы переборные      336
Алгоритмы полиномиальные      168
Алгоритмы приближенные      413
Алгоритмы псевдополиномиальные      168
Алгоритмы субэкспоненциальные      168
Алгоритмы экспоненциальные      168 413
Алмаз      493
Антидерево      414
Арифметическая операция      166
Базис      295
Базисное допустимое решение (бдр)      34
Базисное допустимое решение вырожденное      45
Беглец      193
Блок      28
Булева переменная      323
Булевы формулы      323
Булевы формулы, выполнимые      323
Вектор лексикографически отрицательный      344
Вектор лексикографически положительный      344
Вектор цен      101
Вектор-столбец      25
Вектор-строка      25
Венгерский метод      254 258
Венгерский метод в матричной форме      259
Вершина      25 40
Вершина вырожденная      245
Вершина живая      450
Вершина мертвая      449
Вершина смежная      25
Вершина, степень      25
Вершина, степень захода      26
Вершина, степень исхода      25
Вершинная связность      470
Вершины внешние      224
Вершины внутренние      224
Вершины объединенные в пары      224
Вершины свободные      224
Вершины сети      139
Вершины смежные      65
Веса      287
Ветвление      449 450
Внутренность многогранника      181
Вполне унимодулярность      256
Вращение      181
Время выполнения      319
Выделенный символ      359
Выигрыш      423 479
Выпуклая комбинация      18
Выпуклая комбинация строгая      18
Гамильтонов маршрут      444
Гамильтонов путь      310
Гипергрань      40
Гиперплоскость      38
Гиперплоскость опорная      40
Грани      39 415
Грани смежные      415
Граница      см. «Пропускная способность»
Граф      25
Граф k-регулярный      497
Граф биориентированный      250
Граф взвешенный      27
Граф взвешенный полный      27
Граф двойственный      414
Граф двудольный      26 223
Граф двусвязный      220
Граф диаметр      497
Граф Дирихле      312
Граф допустимый      266
Граф насыщенный      165
Граф ориентированный      см. «Орграф»
Граф пленарный      312
Граф разреженный      165
Граф хордовый      414
Граф эйлеров остовный      424 426
Действительная прямая      24
Дерево      26
Дерево остовное      27
Дефицит      471
Дизъюнкты      323
Динамическое программирование (ДП)      432
Динамическое программирование для задачи о кратчайшем пути в слоистых сетях      461
Динамическое программирование и ЗК      463
Дихотомия      322
Доминирование      456
Дробная часть числа      339
Дуга обратная      125 208
Дуга прямая      124 208
Дуги неособые      130

Дуги особые      130
Задача 0-1-РЮКЗАК      386
Задача 3-ВЫПОЛНИМОСТЬ      369
Задача 3-МЕРНОЕ СОЧЕТАНИЕ      383
Задача 3-РАЗБИЕНИЕ      401
Задача 4-РАЗБИЕНИЕ      414
Задача K-е ПО ВЕСУ МНОЖЕСТВО      408
Задача LP-полная      352 363
Задача m-ЦЛП      414
Задача PSPACE-полная      412
Задача ВЕРШИННОЕ ПОКРЫТИЕ      373 418
Задача ВЕРШИННОЕ ПОКРЫТИЕ, алгоритм 1      418
Задача ВЕРШИННОЕ ПОКРЫТИЕ, алгоритм 2      421
Задача ВЫПОЛНИМОСТЬ      357
Задача выпуклого программирования      9
Задача ГАМИЛЬТОНОВ ЦИКЛ      394
Задача ГАМИЛЬТОНОВА ДОСТРОЙКА      416
Задача главная      102
Задача ГОМЕОМОРФИЗМ ПОДГРАФУ      415
Задача двойственная (Д)      107
Задача двойственная к ограниченной прямой (ДОП)      108 110
Задача ДОПОЛНЕНИЕ ГАМИЛЬТОНОВА ЦИКЛА      394
Задача ДОПОЛНЕНИЕ ЗК      395
Задача ДОПОЛНЕНИЕ СВЯЗНОСТИ
Задача ИЗОМОРФИЗМ ПОДГРАФУ      403
Задача индивидуальная комбинаторная      354
Задача КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ      390
Задача КЛИКА      358
Задача коммивояжера (ЗК)      11 12 359 453
Задача коммивояжера евклидова      423
Задача коммивояжера как задача ЦЛП      317
Задача коммивояжера с неравенством треугольника      423
Задача линейного программирования (ЛП)      9 13
Задача линейного программирования в канонической форме      31
Задача линейного программирования в общей форме      31
Задача линейного программирования в стандартной форме      31 32 175
Задача линейного программирования, двойственная      73
Задача линейного программирования, индивидуальная общая      30
Задача линейного программирования, прямая      73
Задача ЛИНЕЙНЫЕ НЕРАВЕНСТВА (ЛН)      396
Задача МАКСИМАЛЬНОЕ ПАРОСОЧЕТАНИЕ      358
Задача МАКСИМАЛЬНЫЙ РАЗРЕЗ      390
Задача МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО      358
Задача МИНИМАЛЬНОЕ ОСТОВНОЕ ПОКРЫТИЕ      402
Задача МНОГОПРОДУКТОВЫЙ ПОТОК      390
Задача МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ      374
Задача МНОЖЕСТВО ВЕРШИН, РАЗРЕЗАЮЩИХ КОНТУРЫ      390
Задача МНОЖЕСТВО ДУГ, РАЗРЕЗАЮЩИХ КОНТУРЫ      390
Задача НЕЗАВИСИМОЕ МНОЖЕСТВО      373
Задача нелинейного программирования      9
Задача НЕОПТИМАЛЬНОСТЬ В ЗК      495
Задача о b-сочетании      251
Задача о бродячем торговце (ЗБТ)      312
Задача о выполнимости      323
Задача о гамильтоновом пути      302
Задача о диете      30
Задача о китайском почтальоне      276
Задача о китайском почтальоне, смешанный вариант      279 390
Задача о кратчайшем пути (ЗКП)      80 113 451
Задача о кратчайшем пути, веревочная модель      138
Задача о лесе максимального веса (ЛМВ)      287
Задача о линейных неравенствах (ЛН)      176
Задача о максимальной клике      354
Задача о максимальном потоке (ЗМП)      95
Задача о максимальном потоке индивидуальная      95
Задача о максимальном потоке, расширение      232
Задача о матроиде с соответствием      309
Задача о многопродуктовом потоке минимальной стоимости      157
Задача о моменте      23
Задача о надежной сети минимальной стоимости (НСМС)      470
Задача о назначениях      148 159 254 317
Задача о паросочетании      223
Задача о паросочетании в ориентированном графе      251
Задача о паросочетании с весами вершин      312
Задача о паросочетании с узким местом      251
Задача о пересечении двух матроидов      300
Задача о пересечении трех матроидов      309
Задача о подмножествах дискретная линейная (ДЛЗП)      486
Задача о поставщике      156
Задача о потоке минимальной стоимости      141
Задача о равномерном разбиении графа (РРГ)      478
Задача о разбиении относительно матроида      314
Задача о расписании для двух процессоров      250
Задача о расписании для заданий с директивными сроками (РЗДС)      490
Задача о расписании общая      319
Задача о реберном покрытии минимальной стоимости      277
Задача о строгих линейных неравенствах (СЛН)      178
Задача о сумме времен окончания заданий (ЗСВОЗ)      458
Задача о ханойской башне      22
Задача об остовном дереве с пропускными способностями      157
Задача об упаковке контейнеров      252
Задача ОГРАНИЧЕННЫЙ ГАМИЛЬТОНОВ ЦИКЛ (ОГЦ)      492
Задача оптимизации      12
Задача оптимизации индивидуальная      12
Задача оптимизации комбинаторная      354
Задача оптимизации комбинаторная для системы подмножеств      290
Задача оптимизации комбинаторная, вариант вычислительный      355
Задача оптимизации комбинаторная, вариант оптимизационный      355
Задача оптимизации комбинаторная, вариант распознавания      355
Задача ОПТИМИЗАЦИОННЫЙ 0-1-РЮКЗАК      433
Задача ПОСТРОЕНИЕ НАДЕЖНОЙ СЕТИ      403
Задача ПРОБЛЕМА ОСТАНОВКИ      357
Задача ПРОСТЫЕ ЧИСЛА      414
Задача ПРОТЫКАЮЩЕЕ МНОЖЕСТВО      415
Задача прямая (П)      107
Задача ПУТЬ В ОРГРАФЕ      358
Задача РАЗБИЕНИЕ      387
Задача РАСКРАСКА ГРАФА      389
Задача распознавания      357
Задача СВЯЗНОСТЬ ГРАФА      358
Задача ТОЧНОЕ ПОКРЫТИЕ 3-МНОЖЕСТВАМИ      385
Задача ТРАНЗИТИВНОЕ СОКРАЩЕНИЕ ВЫБРАСЫВАНИЕМ      415
Задача Хичкока      148
Задача целочисленного линейного программирования (ЦЛП)      316
Задача целочисленного линейного программирования смешанная (СЦЛП)      319
Задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК      386
Задача, ограниченная прямая (ОП)      108 109
Задачи 0-1-линейного программирования (НОЛП)      324
Задачи NP-полные      11
Задачи NP-полные, частные случаи      413
Задачи выпуклого программирования      21
Задачи двоичного линейного программирования      см. «Задачи 0-1-линейного программирования»
Задачи неразрешимые      160
Задачи о матроидах      280
Задачи о потоках и паросочетаниях      10
Задачи смешанного ЦЛП      333
Задачи целочисленного линейного программирования (ЦЛП)      11
Закорачивание      299
Замещение      48
Запрещение      485
Зацикливание      55
Игра в крестики и нолики n-мерная      193
Инцидентность      25
Исток      27
Источники      203
Клетка Дирихле      311
Клика планарная      404
Комментарии      29
Компонента сильно связная      389
Контейнера вместимость      252
Конус      78
Конъюнктивная нормальная форма      324
Куб      234
Куб d-мерный      171
Куб d-мерный, возмущение      173
Лексикографически больше      344
Лексикографически максимально      344
Лексикографически меньше      344
Лексикографически минимально      344
Лексикографически равно      344

1 2

О проекте