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