Прямолинейное остовное дерево: различия между версиями

== Применение ==

Алгоритм построения прямолинейного минимального остовного дерева широко применяется в САПР для проектирования СБИС. Он часто используется в качестве метрики для оценки длины кабелей в процессе размещения. Прямолинейные МОД нередко вычисляются для аппроксимации дерева Штейнера и являются ключевым компонентом многих эвристик дерева Штейнера. Также они используются для аппроксимации задачи коммивояжера, которая может применяться для генерации цепей сканирования при тестировании. Важно подчеркнуть, что в реальных приложениях размеры входных объектов обычно очень велики. Поскольку эта задача будет вычисляться сотни тысяч раз и во многих случаях на очень больших входных значениях, для вычисления прямолинейного МОД нужен очень эффективный алгоритм.

== Экспериментальные результаты ==

Таблица 1. Экспериментальные результаты.

== См. также ==