Локальные вычисления на графах

Материал из WEGA
Версия от 13:56, 19 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Локальные вычисления на графах''' (''Local computation on graphs'') - метод решения задач ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Локальные вычисления на графах (Local computation on graphs) - метод решения задач на графах, рассматриваемых как вычислительная система, у которой каждая вершина соответствует процессору, а каждое ребро (дуга) --- каналу связи (одностороннему каналу связи). Вся начальная и вычисляемая информация хранится в вершинах в виде меток и доступна только соседним вершинам. Всякие глобальные механизмы, вроде общей памяти, отсутствуют. Успех или неуспех решения задачи зависит только от взаимодействия соседних вершин. Интерес к такого рода вычислениям поддерживается как из-за чисто научных проблем, так и в связи с развитием теории параллельных вычислений. К известным на сегодня результатам следует отнести локальные алгоритмы Ю.И.Журавлева, локальные вычислительные алгоритма В.А.Евстигнеева, интеллигентные графы Э.Розенстиля и др., эхо-алгоритмы Чанга, системы переписывания графов и ряд других.

Литература

{[WG'90]