Том 9, серия 1, номер 2 , 2002 г., Стр. 91-99
УДК 519.17
Н. С. Плеханова, А. В. Пяткин
Передача сообщений в локальной сети с двумя центральными ЭВМ
Аннотация:
ассматривается задача оптимизации времени передачи сообщений в локальной сети с двумя центральными ЭВМ, соединенными между собой шиной с единичной пропускной способностью. Эта задача была сведена к обобщению задачи раскраски инциденторов, в которой помимо инциденторов красятся также средние части некоторых дуг. В случае, когда наибольшая нагрузка приходится на шину, соединяющую центральные ЭВМ, предложен алгоритм для нахождения точного решения с временной сложностью$O(n^2\Delta^2)$ . В противном случае абсолютная погрешность этого алгоритма не превосходит 1.
Ил. 4, библиогр. 7.
Плеханова Н. С. 1
Пяткин А. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 26 декабря 2001 г.
Исправленный вариант — 15 марта 2002 г.
