Жадное встраивание
В распределенных вычислениях и теории геометрических графов жадное внедрение — это процесс присвоения координат узлам телекоммуникационной сети , позволяющий использовать жадную географическую маршрутизацию для маршрутизации сообщений внутри сети. Хотя жадное встраивание было предложено для использования в беспроводных сенсорных сетях , в которых узлы уже имеют позиции в физическом пространстве, эти существующие позиции могут отличаться от позиций, заданных им посредством жадного встраивания, которые в некоторых случаях могут быть точками в виртуальном пространстве. более высокого измерения или в неевклидовой геометрии . В этом смысле жадное встраивание можно рассматривать как форму рисования графа , при которой абстрактный граф (сеть связи) внедряется в геометрическое пространство.
Идея выполнения географической маршрутизации с использованием координат в виртуальном пространстве вместо использования физических координат принадлежит Рао и др. [1] Последующие разработки показали, что каждая сеть имеет жадное вложение с краткими координатами вершин в гиперболической плоскости , что некоторые графы, включая многогранные графы, имеют жадное вложение в евклидовой плоскости и что графы единичного диска имеют жадное вложение в евклидово пространство умеренных размерностей с низкие коэффициенты растяжения.
Определения
[ редактировать ]При жадной маршрутизации сообщение от исходного узла s к узлу назначения t перемещается к месту назначения, пройдя последовательность шагов через промежуточные узлы, каждый из которых передает сообщение соседнему узлу, который находится ближе к t . Если сообщение достигает промежуточного узла x, у которого нет соседа ближе к t , оно не может продвигаться вперед, и процесс жадной маршрутизации завершается неудачей. Жадное вложение — это вложение заданного графа со свойством невозможности отказа данного типа. Таким образом, его можно охарактеризовать как вложение графа со свойством, что для каждых двух узлов x и t существует сосед y узла x такой, что d ( x , t ) > d ( y , t ), где d обозначает расстояние во встроенном пространстве. [2]
Графы без жадного встраивания
[ редактировать ]
Не каждый граф имеет жадное вложение в евклидову плоскость ; простой контрпример даёт звезда К 1,6 , дерево с одним внутренним узлом и шестью листьями. [2] Всякий раз, когда этот граф вкладывается в плоскость, некоторые два его листа должны образовывать угол 60 градусов или меньше, из чего следует, что хотя бы один из этих двух листьев не имеет соседа, находящегося ближе к другому листу.
В евклидовых пространствах более высоких измерений большее количество графов может иметь жадные вложения; например, K 1,6 имеет жадное вложение в трехмерное евклидово пространство, в котором внутренний узел звезды находится в начале координат, а листья - на расстоянии единицы вдоль каждой оси координат. Однако для любого евклидова пространства фиксированной размерности существуют графы, которые не могут быть вложены жадно: всякий раз, когда число n больше числа поцелуев пространства, граф K 1, n не имеет жадного вложения. [3]
Гиперболические и краткие вложения
[ редактировать ]В отличие от случая с евклидовой плоскостью, каждая сеть имеет жадное вложение в гиперболическую плоскость . Первоначальное доказательство этого результата, предложенное Робертом Кляйнбергом , требовало указания положений узлов с высокой точностью: [4] но впоследствии было показано, что, используя сети по тяжелым путям разложение остовного дерева , можно кратко представить каждый узел, используя только логарифмическое число битов на точку. [3] Напротив, существуют графы, которые имеют жадные вложения в евклидову плоскость, но для которых любое такое вложение требует полиномиального числа бит для декартовых координат каждой точки. [5] [6]
Специальные классы графов
[ редактировать ]Деревья
[ редактировать ]Класс деревьев , допускающих жадные вложения в евклидову плоскость, полностью охарактеризован, и жадное вложение дерева может быть найдено за линейное время , когда оно существует. [7]
Для более общих графов можно использовать некоторые жадные алгоритмы встраивания, такие как алгоритм Кляйнберга. [4] начните с поиска остовного дерева данного графа, а затем постройте жадное вложение остовного дерева. Результатом также является жадное встраивание всего графа. Однако существуют графы, имеющие жадное вложение в евклидовой плоскости, но для которых ни одно остовное дерево не имеет жадного вложения. [8]
Планарные графы
[ редактировать ]Пападимитриу и Ратайчак (2005) предположили , что каждый многогранный граф ( с 3-связными вершинами планарный граф или, что то же самое, по теореме Стейница, график выпуклого многогранника ) имеет жадное вложение в евклидову плоскость. [2] Используя свойства кактусовых графов , Лейтон и Мойтра (2010) доказали гипотезу; [8] [9] жадные вложения этих графов можно определить кратко, с логарифмическим количеством битов на координату. [10] Однако жадные вложения, построенные согласно этому доказательству, не обязательно являются плоскими вложениями, поскольку они могут включать в себя пересечения между парами ребер. Для максимальных планарных графов , в которых каждая грань представляет собой треугольник, жадное плоское вложение можно найти, применив лемму Кнастера – Куратовского – Мазуркевича к взвешенной версии алгоритма линейного вложения Шнайдера. [11] [12] Сильная гипотеза Пападимитриу–Ратайчака о том, что каждый многогранный граф имеет плоское жадное вложение, в котором все грани выпуклы, остается недоказанной. [13]
Дисковые графы единиц
[ редактировать ]Беспроводные сенсорные сети, являющиеся целью жадных алгоритмов внедрения, часто моделируются как графы единичных дисков , графы, в которых каждый узел представлен как единичный диск , а каждое ребро соответствует паре дисков с непустым пересечением. Для этого специального класса графов можно найти краткие жадные вложения в евклидово пространство полилогарифмической размерности с дополнительным свойством, заключающимся в том, что расстояния в графе точно аппроксимируются расстояниями во вложении, так что пути, по которым следует жадная маршрутизация, равны короткий. [14]
Ссылки
[ редактировать ]- ^ Рао, Анант; Ратнасами, Сильвия; Пападимитриу, Христос Х .; Шенкер, Скотт ; Стойка, Ион (2003), «Географическая маршрутизация без информации о местоположении», Proc. 9-я конференция ACM Mobile Computing and Networking (MobiCom) , стр. 96–108, doi : 10.1145/938985.938996 , S2CID 8374920 .
- ^ Jump up to: а б с Пападимитриу, Христос Х .; Ратайчак, Дэвид (2005), «О гипотезе, связанной с геометрической маршрутизацией», Theoretical Computer Science , 344 (1): 3–14, doi : 10.1016/j.tcs.2005.06.022 , MR 2178923 .
- ^ Jump up to: а б Эппштейн, Д .; Гудрич, М.Т. (2011), «Краткая жадная геометрическая маршрутизация с использованием гиперболической геометрии», IEEE Transactions on Computers , 60 (11): 1571–1580, doi : 10.1109/TC.2010.257 , S2CID 40368995 .
- ^ Jump up to: а б Кляйнберг, Р. (2007), «Географическая маршрутизация с использованием гиперболического пространства», Proc. 26-я Международная конференция IEEE по компьютерным коммуникациям (INFOCOM 2007) , стр. 1902–1909, doi : 10.1109/INFCOM.2007.221 , S2CID 11845175 .
- ^ Цао, Лей; Стрельцов А.; Сан, Дж.З. (2009), «О краткости геометрической жадной маршрутизации в евклидовой плоскости», 10-й Международный симпозиум по всеобъемлющим системам, алгоритмам и сетям (ISPAN 2009) , стр. 326–331, doi : 10.1109/I-SPAN.2009.20 , S2CID 6513298 .
- ^ Анджелини, Патрицио; Ди Баттиста, Джузеппе; Фрати, Фабрицио (2010), «Краткие жадные рисунки не всегда существуют», Рисование графиков: 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Переработанные статьи , Конспекты лекций по информатике, том . 5849, стр. 171–182, номер документа : 10.1007/978-3-642-11805-0_17 , ISBN. 978-3-642-11804-3 .
- ^ Нёлленбург, Мартин; Пруткин, Роман (2013), «Евклидовы жадные рисунки деревьев», Учеб. 21-й Европейский симпозиум по алгоритмам (ESA 2013) , arXiv : 1306.5224 , Bibcode : 2013arXiv1306.5224N .
- ^ Jump up to: а б Лейтон, Том ; Мойтра, Анкур (2010), «Некоторые результаты по жадным вложениям в метрические пространства», Дискретная и вычислительная геометрия , 44 (3): 686–705, doi : 10.1007/s00454-009-9227-6 , MR 2679063 .
- ^ Анджелини, Патрицио; Фрати, Фабрицио; Грилли, Лука (2010), «Алгоритм построения жадных рисунков триангуляций», Журнал графовых алгоритмов и приложений , 14 (1): 19–51, doi : 10.7155/jgaa.00197 , MR 2595019 .
- ^ Гудрич, Майкл Т .; Стрэш, Даррен (2009), «Краткая жадная геометрическая маршрутизация в евклидовой плоскости», Алгоритмы и вычисления: 20-й международный симпозиум, ISAAC 2009, Гонолулу, Гавайи, США, 16–18 декабря 2009 г., Труды , конспекты лекций по информатике, том. 5878, Берлин: Springer, стр. 781–791, arXiv : 0812.3893 , doi : 10.1007/978-3-642-10631-6_79 , ISBN 978-3-642-10630-9 , МР 2792775 , S2CID 15026956 .
- ^ Шнайдер, Уолтер (1990), «Вложение плоских графов в сетку», Proc. 1-й симпозиум ACM/SIAM по дискретным алгоритмам (SODA) , стр. 138–148 .
- ^ Дхандапани, Рагхаван (2010), «Жадные рисунки триангуляции», Дискретная и вычислительная геометрия , 43 (2): 375–392, doi : 10.1007/s00454-009-9235-6 , MR 2579703 , S2CID 11617189 . См. также
- ^ Нёлленбург, Мартин; Пруткин Роман; Раттер, Игнац (2016), «О рисунках трехсвязных плоских графов с самоподходом и возрастающей хордой», Journal of Computational Geometry , 7 (1): 47–69, arXiv : 1409.0315 , doi : 10.20382/jocg.v7i1a3 , МР 3463906 , S2CID 1500695 .
- ^ Флюри, Р.; Пеммараджу, СВ; Ваттенхофер, Р. (2009), «Жадная маршрутизация с ограниченным растяжением», IEEE Infocom 2009 , стр. 1737–1745, doi : 10.1109/INFCOM.2009.5062093 , ISBN 978-1-4244-3512-8 , S2CID 1881560 .