Введение
1. Введение 4
1.1. Цели и задачи 4
1.2. Постановки задачи Штейнера 5
1.3. Применение 6
1.3.1. VLSI-проектирование 6
1.3.2. Восстановление филогенетических деревьев 8
1.3.3. Интерактивная телекоммуникация 9
1.4. Описание работы по главам 10
1.5. Основные определения и обозначения 13
2. Состояние дел 15
2.1. Точные алгоритмы 15
2.1.1. Алгоритм динамического программирования 16
2.1.2. Сведение к задаче линейного программирования 18
2.2. Приближенные алгоритмы 21
2.2.1. Алгоритм Такахаши-Мацуямы 22
2.2.2. Приближенные алгоритмы основанные на линейном программировании 23
2.2.3. Жадные алгоритмы 28
3. Алгоритм /с-кластерной оптимизации 33
3.1. Определение кластеров в графе 34
3.1.1. Построение опорного дерева 34
3.1.2. Разбиение на кластеры 35
3.2. Построение деревьев Штейнера на кластерах 37
3.3. Улучшение деревьев Штейнера на кластерах 38 3.4. Нахождение промежуточного полного дерева Штейнера 38
3.5. Улучшение промежуточного дерева Штейнера 39
3.6. Теорема о вычислительной сложности 40
4. Приближенный метод 3 для задачи Штейнера на евклидовых графах 47
4.1. Алгоритм А поиска кратчайшего пути 47
4.2. Задача Штейнера на концентрических окружностях 50
4.3. Алгоритм S на евклидовых графах 53
4.3.1. Построение приближенного решения 53
4.3.2. Построение множества терминальных подмножеств. Наивный метод 54
4.3.3. Построение множества терминальных подмножеств. Метод «концентрических окружностей» 56
4.3.4. Построение множества терминальных подмножеств. Обобщенный метод 58
4.3.5. Теоретические результаты 59
5. Вычислительные оптимизации 62
5.1. Общий обзор 62
5.2. Особенности реализации однопоточных алгоритмов 63
5.2.1. Алгоритм динамического программирования 63
5.2.2. /с-кластерный приближенный алгоритм 73
5.2.3. Приближенный метод S на евклидовых графах 76
5.3. Параллелизация алгоритмов 81
5.3.1. Параллелизация точного алгоритма решения 5.3.2. Параллелизация алгоритма / -кластерной оптимизации 89
5.3.3. Параллелизация алгоритма аппроксимации S 91
6. Вычислительные результаты 93
6.1. Сравнение эффективности структур, реализующих приоритетную очередь 93
6.2. Сравнение эффективности -кластерного метода с другими известными 95
6.3. Сравнение эффективности метода S с другими известными 97
6.4. Сравнение быстродействия однопоточных и параллельных реализаций методов 102
6.4.1. Метод динамического программирования 102
6.5. Метод к-кластерной оптимизации 104
6.6. Метод 5 105
7. Результаты и выводы 108
