4551
правка
Распределенные алгоритмы для минимальных остовных деревьев: различия между версиями
Перейти к навигации
Перейти к поиску
Распределенные алгоритмы для минимальных остовных деревьев (посмотреть исходный код)
Версия от 23:34, 28 ноября 2013
, 28 ноября 2013→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
В этой области остается множество открытых вопросов. Хотя асимптотически жесткая граница сложности по сообщениям O(m + n log n) для задачи нахождения MST в графах общего вида известна, проблема нахождения фактических ограничений остается нерешенной. Однако для остовных деревьев общего вида, в отличие от минимальных, существуют константы меньшей величины [6]. | В этой области остается множество открытых вопросов. Хотя асимптотически жесткая граница сложности по сообщениям O(m + n log n) для задачи нахождения MST в графах общего вида известна, проблема нахождения фактических ограничений остается нерешенной. Однако для остовных деревьев общего вида, в отличие от минимальных, существуют константы меньшей величины [6]. | ||
Как упоминалось выше, в работе [] и содержащихся в ней ссылках можно найти сведения об алгоритмах, близких к оптимальным по времени, и нижних границах. Задача достижения оптимальной временной сложности остается нерешенной. Кроме того, в синхронной модели для наложенных сетей, в которых все процессоры напрямую связаны друг с другом, MST может быть построено за сублогарифмическое время, а именно – за O( | Как упоминалось выше, в работе [10] и содержащихся в ней ссылках можно найти сведения об алгоритмах, близких к оптимальным по времени, и нижних границах. Задача достижения оптимальной временной сложности остается нерешенной. Кроме того, в синхронной модели для наложенных сетей, в которых все процессоры напрямую связаны друг с другом, MST может быть построено за сублогарифмическое время, а именно – за O(log log n) эпизодов коммуникации [9], и нижняя граница для него неизвестна. | ||
== См. также == | == См. также == | ||