5370

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Преобразование сетевого графика задач теории расписаний с ограничениями предшествования

Наименование источника: 

  • Доклады Академии наук

Обозначение и номер тома: 

Т.424, №1

Город: 

  • Москва

Издательство: 

  • Наука

Год издания: 

2008

Страницы: 

7-9
Аннотация
Для задач на графах построен алгоритм трудоёмкости О(n^5), где n - количество вершин в графе, преобразующий непланарный неориентированный граф в планарный. В результате получается планарный граф,у которого сумма вершин и рёбер не больше, чем у исходного непланарного графа. Причём, если между вершинами i и j был путь, то он сохраниться, если не было такого пути, то он и не появится.

Библиографическая ссылка: 

Лазарев А.А., Гафаров Е.Р. Преобразование сетевого графика задач теории расписаний с ограничениями предшествования // Доклады Академии наук. 2008. Т.424, №1. С. 7-9.