Семинары: А. Березин, И. А. Вакула, С. Леонова, Пути максимального веса в вершинно-взвешенных ориентированных графах специального вида

СЕМИНАРЫ


Семинар отдела математического программирования 16 мая 2014 г. 11:00, г. Екатеринбург, ул. Софьи Ковалевской, 16, актовый зал, 3 этаж, Институт математики и механики им. Красовского

Пути максимального веса в вершинно-взвешенных ориентированных графах специального вида А. Березин, И. А. Вакула, С. Леонова Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
Аннотация: Рассматривается задача построения путей максимального веса в вершинно-взвешенных графах специального вида. Графы и рассматриваемая постановка поиска путей связаны с задачей планирования прокатки на станах горячей и холодной прокатки. Опираясь на особенности рассматриваемых графов авторами построен алгоритм сложности $O(n^3),$ в то же время в общем случае задача NP-трудна. Планируется также обсудить направления дальнейших исследований и прикладное значение результатов работы.