Автор(ы): Лазарев А. А. (ИПУ РАН, Лаборатория 68)Гафаров Е. Р. (ИПУ РАН, Лаборатория 68)Автор(ов): 2 Параметры публикацииТип публикации: Статья в журнале/сборникеНазвание: Преобразование сетевого графика задач теории расписаний с ограничениями предшествованияНаименование источника: Доклады Академии наукОбозначение и номер тома: Т.424, №1Город: МоскваИздательство: НаукаГод издания: 2008Страницы: 7-9 АннотацияДля задач на графах построен алгоритм трудоёмкости О(n^5), где n - количество вершин в графе, преобразующий непланарный неориентированный граф в планарный. В результате получается планарный граф,у которого сумма вершин и рёбер не больше, чем у исходного непланарного графа. Причём, если между вершинами i и j был путь, то он сохраниться, если не было такого пути, то он и не появится. Библиографическая ссылка: Лазарев А.А., Гафаров Е.Р. Преобразование сетевого графика задач теории расписаний с ограничениями предшествования // Доклады Академии наук. 2008. Т.424, №1. С. 7-9.