Аннотация:
Описывается win-win алгоритм, строящий за полиномиальное от $|V(G)|$ и $k$ время для любого графа $G$ и любого натурального числа $k$ либо остовное дерево с хотя бы $k+1$ листьями, либо предоставляет путевое представление (path decomposition) ширины не большей $k$. Данный алгоритм оптимален в силу следствия теоремы о путевом представлении [1]. Библиогр. 5.