Алгоритмы поиска остова во взвешенном графе: различия между версиями

Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют дуги разреженного остова для маршрутизации сообщений. В распределенных системах остовы играют важную роль при разработке синхронизаторов. Авербух [3] и Пелег и Ульман [15] показали, что качество остова (выражаемое в терминах коэффициента растяжения и количества дуг остова) тесно связано с временем и вычислительной сложностью любого синхронизатора сети. Остовы также могут неявно использоваться во множестве алгоритмов для вычисления всех пар аппроксимированных кратчайших путей [5, 9, 18]. Примеры других приложений можно найти в работах [2, 3, 14, 16].