Задача построения синхронизирующего сигнального дерева

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

Статья представлена к публикации членом редколлегии: В. М. Вишневский