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

Выбор оптимальных соединений в дереве с учетом задержек Эльмора

Авторы
 Ерзин А.И.
Год публикации
 2006
УДК
 621.38

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

Copyright © 2009-2018 ИППМ РАН. All Rights Reserved.

Разработка сайта - ИППМ РАН