Параллельный алгоритм Соллина поиска остовного дерева

Авторы
Файлы

Салпагаров С.И. Статья в формате PDF 160 KB

Рассмотрим взвешенный предфpaктальный [1], (n, L) - граф G = (V,E) и траекторию G₁ = (V₁,E₁), l=1,2,...,L. Пусть имеется k процессов [2] p1,p2,...,pk, где и каждый из k процессоров, назначен одной из затравок

Множество всех затравок Z_s ^(l) всех рангов предфpaктального (n, L), графа G = (V,E) обозначим через ,

Идея работы параллельного алгоритма Соллина α поиска остовного дерева минимального веса [3] заключается в следующем.

Каждая затравка рассматривается как отдельный подграф, и k процессоров p₁, p₂,..., p_k параллельно и независимо друг от друга находят остовные деревья минимально- го веса (ОДМВ), каждый на своей назначенной затравке Z_s^(l) . Объединяя полученные результаты, т.е. выделенные ОДМВ, получим ОДМВ предфpaктального (n,L)-графа G=(V, Е). Обосно- ванием работы алгоритма Соллина α являются следующие теоремы:

Теорема 1. Параллельный алгоритм Соллина α строит на предфpaктальном (n,L)-графе G=(V, Е), остовное дерево минимального веса Т=(V, Е_S).

Теорема 2. Вычислительная сложность алгоритма Соллина для связного взвешенного графа G=(V,E), |V|=n, |E|=m, где имеется n процессоров (компьютеров) p₁,p₂,…p_n, каждый из которых назначен одной из вершин v₁,v₂,…,v_n графа G=(V, E), равна Z_s^(l) О(n²log² n).

Литература

Кочкаров А.М. Распознавание фpaктальных графов. Алгоритмический подход. Нижний Архыз: САО РАН.-1998.
Воеводин В.В. Математические модели и методы в параллельных процессах.М.: Наука, 1986.
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.: Мир, 1981

Пролиферативная активность и апоптоз эпителиоцитов пищевода при гастроэзофагеальной рефлюксной болезни и пищеводе Баррета

Статья в формате PDF 110 KB...

02 07 2026 7:12:23

ВЛИЯНИЕ ОБРАЗОВАТЕЛЬНОГО ПРОСТРАНСТВА ТЕХНИЧЕСКОГО ВУЗА НА ФОРМИРОВАНИЕ ПРОФЕССИОНАЛЬНЫХ КОМПЕТЕНЦИЙ СТУДЕНТОВ

Статья в формате PDF 270 KB...

01 07 2026 20:53:19

ВОЗДЕЙСТВИЕ ПОВЕРХНОСТНОЙ РЕФЛЕКСОТЕРАПИИ (ИППЛИКАТОРА РЕДОКС) НА СПЕКТРАЛЬНЫЕ ХАРАКТЕРИСТИКИ СИСТЕМЫ КРОВООБРАЩЕНИЯ

Статья в формате PDF 108 KB...

30 06 2026 0:49:34

ИНТРОДУКЦИОННЫЙ ПОИСК ПЕРСПЕКТИВНЫХ РАСТЕНИЙ СЕМЕЙСТВА RANUNCULACEAEJ.

Статья в формате PDF 379 KB...

29 06 2026 17:52:44

К ВОПРОСУ О ВИБРОАКУСТИЧЕСКОЙ ДИАГНОСТИКЕ МАШИН И ОБОРУДОВАНИЯ

Статья в формате PDF 128 KB...

28 06 2026 20:59:15

СПЕЦИАЛИЗИРОВАННЫЕ АЛГОРИТМЫ ОБУЧЕНИЯ И НАСТРОЙКИ РЕКУРРЕНТНОЙ СЕТИ ПРЕОБРАЗОВАТЕЛЯ ЧАСТОТНО-ВРЕМЕННЫХ ПАРАМЕТРОВ СИГНАЛОВ В КОД

Статья в формате PDF 148 KB...

27 06 2026 3:14:22

ПРОТИВОРЕЧИЯ ИНТЕРЕСОВ ПЕРЕХОДНОЙ ЭКОНОМИКИ И ПУТИ ИХ СОГЛАСОВАНИЯ В УСЛОВИЯХ ЭКОЛОГИЧЕСКОГО НЕРАВНОВЕСИЯ

Статья в формате PDF 149 KB...

26 06 2026 12:10:34

СМЕРТНАЯ КАЗНЬ В ЗЕРКАЛЕ РУССКОЙ КУЛЬТУРЫ И ФИЛОСОФИИ

В данной работе автор отвергает идею принятия cмepтной казни. Применение cмepтной казни приведет к нарушению природы государства, вырождению его духовной сущности. Если государство допускает возможность cмepтной казни, то ценность человеческой жизни падает, а для самих исполнителей cмepтной казни убийство станет обычным явлением. ...

25 06 2026 19:12:23

ОСОБЕННОСТИ ПРОЕКТИРОВАНИЯ И ПОДГОТОВКИ УЧЕБНОГО ЗАНЯТИЯ В ВУЗЕ

Статья в формате PDF 300 KB...

24 06 2026 8:24:52

ОБУЧЕНИЕ В ВУЗЕ ПО СИСТЕМЕ ШАТАЛОВА (научно-методическое пособие)

Статья в формате PDF 108 KB...

23 06 2026 14:14:55

КЛИНИЧЕСКАЯ ПОЛИФОНИЯ ЗАСТАРЕЛОГО РОТАЦИОННОГО ПОДВЫВИХА С1 У ДЕТЕЙ

Статья в формате PDF 126 KB...

22 06 2026 23:17:12

ОПЫТ ПРИМЕНЕНИЯ МЕТОДА АГРОСТЕПЕЙ ДЛЯ ВОССТАНОВЛЕНИЯ НАРУШЕННОЙ РАСТИТЕЛЬНОСТИ ДОЛИНЫ СРЕДНЕЙ ЛЕНЫ (ЦЕНТРАЛЬНАЯ ЯКУТИЯ)

Анализ опыта по восстановлению методом агростепей растительности на нарушенных кормовых угодьях долины средней Лены показал, что метод при соблюдении экологических условий и видового состава участков обеспечивает восстановление растительности, проявляющееся в повышении проективного покрытия и доминировании в травостое целинных видов. Соответствие экологических условий и видового состава травостоя при подборе участков обеспечивает восстановление растительности нарушенных участков до 70–75 % и доминирование в травостое целинных видов до 60–65 % в условиях нормального и сильного засоления. ...