4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 16:53, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 85: | Строка 85: | ||
2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей <math>E_2 (x) \; </math>, определяемое следующим образом: <math>E_2 (x) = \{ uv \in S \Theta\ GG | u</math> или <math>v \in N_{UDG}(X) \} </math>. Иными словами, ЕгМ представляет собой набор дуг в <math>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x. | 2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей <math>E_2 (x) \; </math>, определяемое следующим образом: <math>E_2 (x) = \{ uv \in S \Theta\ GG | u</math> или <math>v \in N_{UDG}(X) \} </math>. Иными словами, ЕгМ представляет собой набор дуг в <math>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x. | ||
3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в | 3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в <math>E_2 (x) \; </math>, он удаляет дугу xy в случае, если существует дуга <math>uv \in E_2 (x) \; </math> (где u и v отличны от x и y), такая, что <math>\big\| xy \big\| > max( \big\| uv \big\|, 3\big\| ux \big\|, 3\big\| vy \big\|)</math>; в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при помощи широковещательного сообщения UPDATESTATUS(XY). | ||
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в | 4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в <math>E_2 (u) \; </math>. | ||
5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися дугами в <math>S \Theta\ GG</math>. | 5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за <math>LS \Theta\ GG</math> финальную структуру, сформированную всеми оставшимися дугами в <math>S \Theta\ GG</math>. | ||