Институт вычислительной математики и математической геофизики СОРАН

Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем"

Кыргызская Республика, г.Бишкек, база "Эдельвейс" Иссык-Кульского Государственного Университета, 12 - 22 августа.
ВАЖНАЯ ИНФОРМАЦИЯ

Тезисы докладов

О некоторых задачах передачи информации

Юргенсон А.Н., Соколова О.Д.

Институт вычислительной математики и математической геофизики СО РАН (Новосибирск)

В докладе рассматривается одна из актуальных задач, возникающих при передаче информации по сети, в которой различные каналы имеют различную стоимость за пересылку единицы информации. Требуется разослать из пункта-источника некоторый объем информации в некоторые узлы сети, чтобы при этом общая стоимость пересылки была минимальной. Сеть передачи данных моделируется графом, и данная задача сводится к известной задачи теории графов – поиску дерева Штейнера, которая является NP-полной. Для решения задачи был разработан эвристический полиномиальный алгоритм на основе известного алгоритма Краскала (Kruskal) поиска минимального остовного дерева на графе

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)