Локальные вычисления в неструктурированных радиосетях: различия между версиями

В последующей работе [18] было показано, что времени выполнения <math>O(log^2 \; n)</math> достаточно даже для вычисления более сложной структуры максимального независимого множества. Этот результат является асимптотически оптимальным, поскольку, улучшая ранее известное ограничение <math>\Omega(log^2 \; n / log \; log \; n)</math> [9], в [6] было доказано соответствующее нижнее ограничение <math>\Omega(log^2 \; n)</math>.

Любопытно сравнить эту достижимую верхнюю границу для жесткой модели неструктурированной радиосети с лучшими известными нижними границами времени выполнения у моделей передачи сообщений: <math>\Omega(log^* \; n)</math> на графах единичных дисков [12] и <math>\Omega(\sqrt{log \; n / log \; log \; n})</math> на графах общего вида [11]. Кроме того, в [7] была доказана временная граница <math>O(log^2 \; n)</math> в модели радиосети без асинхронного пробуждения, в которой узлы априори знают своих соседей. Наконец, также можно эффективно раскрашивать узлы сети, как было показано в [17], а затем улучшено и обобщено в главе 12 работы [15].