Передача сообщений в локальной сети с двумя центральными ЭВМ

Рассматривается задача оптимизации времени передачи сообщений в локальной сети с двумя центральными ЭВМ, соединенными между собой шиной с единичной пропускной способностью. Эта задача была сведена к обобщению задачи раскраски инциденторов, в которой помимо инциденторов красятся также средние части некоторых дуг. В случае, когда наибольшая нагрузка приходится на шину, соединяющую центральные ЭВМ, предложен алгоритм для нахождения точного решения с временной сложностью $O(n^2\Delta^2)$. В противном случае абсолютная погрешность этого алгоритма не превосходит 1.
Ил. 4, библиогр. 7.