Просмотр кода страницы Локальные вычисления на графах

'''Локальные вычисления на графах''' (''[[Local computation on graphs]]'') — метод решения задач на [[граф|графах]], рассматриваемых как вычислительная система, у которой каждая [[вершина]] соответствует процессору, а каждое [[ребро]] ([[дуга]]) — каналу связи (одностороннему каналу связи). Вся начальная и вычисляемая информация хранится в вершинах в виде меток
и доступна только соседним вершинам. Всякие глобальные механизмы,
вроде общей памяти, отсутствуют. Успех или неуспех решения задачи
зависит только от взаимодействия соседних вершин. Интерес к такого
рода вычислениям поддерживается как из-за чисто научных проблем, так и
в связи с развитием теории параллельных вычислений. К известным на
сегодня результатам следует отнести локальные алгоритмы Ю.И.Журавлева,
локальные вычислительные алгоритмы В.А.Евстигнеева, интеллигентные
графы Э.Розенстиля и др., эхо-алгоритмы Чанга, ''[[Система переписывания графов (с приоритетами)|системы переписывания графов]]'' и ряд других.
==Литература==
* Workshop. Berlin, 1990 // Lect. Notes Comp. Sci., 1991, vol. 484.