Аннотация:
В работе представлен рекурсивный подход к решению задачи “Линейное размещение графа по длине”. Представлен критерий минимальности размещения, с помощью которого получено упрощенное доказательство полиномиальной разрешимости задачи в классе двудольных, $\Gamma$-ориентированных графов.
Ключевые слова:MINLA, graph linear arrangement, $\Gamma$-oriented graphs.