Аннотация:
Рассматривается задача минимальной укладки дерева на отрезок. Известно, что для деревьев с незакрепленными вершинами она решается за полиномиальное время. Здесь устанавливается, что при закреплении некоторых вершин дерева эта задача становится NP-полной.