Главная         Авторы   Статьи   Год проведения   Тематика   Организации        Конференция МЭС

Выбор оптимальных соединений в дереве с учетом задержек Эльмора
Авторы
	Ерзин А.И.
Год публикации
	2006
УДК
	621.38
Аннотация
	Рассматривается задача выбора оптимальных типов соединений на ребрах заданного дерева с выделенной корневой вершиной – источником сигнала и подмножеством вершин-терминалов (получателей сигнала). Для каждого терминала задан допустимый интервал времени, в течение которого сигнал должен быть получен. Время получения сигнала вычисляется по формулам Эльмора. Требуется выбрать такие типы соединений, при которых время прихода сигнала в каждый терминал допустимо, а суммарная емкость дерева минимальна. Предложен новый алгоритм однопараметрического динамического программирования трудоемкости O(nXD2), где n – число вершин дерева, D – максимально допустимая задержка, а X – максимальное количество типов соединений, которые могут использоваться на одном ребре.
Ключевые слова
	оптимальные соединения
Ссылка на статью
	Ерзин А.И. Выбор оптимальных соединений в дереве с учетом задержек Эльмора // Проблемы разработки перспективных микроэлектронных систем - 2006. Сборник научных трудов / под общ. ред. А.Л.Стемпковского. М.:ИППМ РАН, 2006. С. 109-114.
Адрес статьи
	http://www.mes-conference.ru/data/year2006/18.pdf