Том 7, серия 2, номер 1, 2000 г., Стр. 61-64
УДК 519.854.2
Г. Г. Забудский
О задаче линейного упорядочения вершин параллельно-последовательных графов
Аннотация:
Изучается задача о размещении вершин ориентированного графа в целые точки числовой прямой, при котором сохраняется частичный порядок, задаваемый графом, и минимизируется взвешенная сумма длин всех дуг. Показано, что для параллельно-последовательных графов задача решается за полиномиальное время.
Библиогр. 4.
Забудский Г. Г. 1
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: zabudsky@iitam.omsk.net.ru
Статья поступила 18 июня 1998 г.
Исправленный вариант — 7 февраля 2000 г.
