Введение
Глава 1. Определения и понятия 9
1.1 Элементы теории графов, используемые в работе 9
1.2 Место минимальных связывающих деревьев в задачах САПР электронной аппаратуры 15
1.3 Задача Краскала-Прима. 22
1.4 Выводы 29
Глава 2. Задача Штейнера 30
2.1 Свойства деревьев Штейнера в прямоугольной метрике 32
2.2 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для задач ограниченной размерности 33
2.3 Точные алгоритмы построения деревьев Штейнера в прямоугольной метрике для общего случая 37
2.4 Приближенные алгоритмы построения деревьев Штейнера в прямоугольной метрике ...41
2.5 Алгоритм выборки перспективных дополнительных точек 51
2.6 Оптимизация конфигурации дерева Штейнера... 68
2.7 Выводы 79
Глава 3. Глобальная трассировка 81
3.1 Постановка задачи и стандартная методика глобальной трассировки 1 81
3.2 Первый этап Pathfinder. Построение леса деревьев с учетом текущего распределения цепей по ребрам глобального графа ... 88
3.3 Второй этап Pathfinder. Оптимизация распределения цепей по ребрам глобального графа 100
3.4 Третий этап Pathfinder. Волновая трассировка 109
3.5 Сравнение результатов Pathfinder с результатами других программ глобальной трассировки 111
3.6 Выводы 114
Заключение 116
Благодарности 117
