О задаче линейного упорядочения вершин параллельно-последовательных графов

Изучается задача о размещении вершин ориентированного графа в целые точки числовой прямой, при котором сохраняется частичный порядок, задаваемый графом, и минимизируется взвешенная сумма длин всех дуг. Показано, что для параллельно-последовательных графов задача решается за полиномиальное время. Библиогр. 4.