Жадное вложение - Greedy embedding

В распределенных вычислений и геометрическая теория графов, жадное вложение представляет собой процесс присвоения координат узлам телекоммуникационная сеть чтобы позволить жадный географическая маршрутизация для маршрутизации сообщений в сети. Хотя жадное встраивание было предложено для использования в беспроводные сенсорные сети, в котором узлы уже имеют позиции в физическом пространстве, эти существующие позиции могут отличаться от позиций, данных им жадным встраиванием, которые в некоторых случаях могут быть точками в виртуальном пространстве более высокого измерения или в неевклидова геометрия. В этом смысле жадное вложение можно рассматривать как форму рисунок графика, в котором абстрактный граф (сеть связи) встроенный в геометрическое пространство.

Идея выполнения географической маршрутизации с использованием координат в виртуальном пространстве вместо использования физических координат принадлежит Рао и др.[1] Дальнейшие разработки показали, что каждая сеть имеет жадное вложение с краткими координатами вершин в гиперболическая плоскость, что некоторые графики, включая многогранные графы жадно встраиваются в Евклидова плоскость, и это графы единичного диска имеют жадные вложения в евклидовы пространства умеренных размеров с низкими факторами растяжения.

Определения

В жадной маршрутизации сообщение от исходного узла s к узлу назначения т перемещается к месту назначения посредством последовательности шагов через промежуточные узлы, каждый из которых передает сообщение соседнему узлу, который находится ближе к т. Если сообщение достигает промежуточного узла Икс у которого нет соседа ближе к т, то он не сможет продвинуться вперед, и процесс жадной маршрутизации завершится ошибкой. Жадное вложение - это вложение данного графа, обладающее тем свойством, что отказ данного типа невозможен. Таким образом, его можно охарактеризовать как вложение графа со свойством, что для каждых двух узлов Икс и т, существует сосед у из Икс такой, что d(Икс,т) > d(у,т), куда d обозначает расстояние во вложенном пространстве.[2]

Графы без жадного вложения

K1,6, граф без жадного вложения в Евклидова плоскость

Не каждый граф имеет жадное вложение в Евклидова плоскость; простой контрпример дается звезда K1,6, а дерево с одним внутренним узлом и шестью листами.[2] Всякий раз, когда этот граф вложен в плоскость, некоторые два его листа должны образовывать угол 60 градусов или меньше, из чего следует, что по крайней мере один из этих двух листов не имеет соседа, который находится ближе к другому листу.

В Евклидовы пространства для более высоких измерений большее количество графов может иметь жадные вложения; например, K1,6 имеет жадное вложение в трехмерное евклидово пространство, в котором внутренний узел звезды находится в начале координат, а листья расположены на единичном расстоянии вдоль каждой координатной оси. Однако для каждого евклидова пространства фиксированной размерности есть графы, которые нельзя жадно вложить: всякий раз, когда число п больше, чем номер поцелуя пространства, граф K1,п не имеет жадных вложений.[3]

Гиперболические и сжатые вложения

В отличие от евклидовой плоскости, каждая сеть жадно встраивается в гиперболическая плоскость. Первоначальное доказательство этого результата Роберт Клейнберг, требовал, чтобы положения узлов были указаны с высокой точностью,[4] но впоследствии было показано, что с помощью разложение тяжелого пути из остовное дерево сети можно кратко представить каждый узел, используя только логарифмическое количество битов на точку.[3] Напротив, существуют графы, которые имеют жадные вложения в евклидову плоскость, но для которых любое такое вложение требует полиномиального количества бит для декартовых координат каждой точки.[5][6]

Специальные классы графов

Деревья

Класс деревья которые допускают жадные вложения в евклидову плоскость, полностью охарактеризованы, а жадные вложения дерева можно найти в линейное время когда он существует.[7]

Для более общих графов используются некоторые жадные алгоритмы вложения, такие как алгоритм Клейнберга.[4] начни с поиска остовное дерево данного графа, а затем построить жадное вложение остовного дерева. Результатом обязательно будет жадное вложение всего графа. Однако существуют графы, которые имеют жадное вложение в евклидову плоскость, но для которых ни одно остовное дерево не имеет жадного вложения.[8]

Планарные графики

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Каждый многогранный граф есть плоское жадное вложение с выпуклыми гранями?
(больше нерешенных задач по математике)

Пападимитриу и Ратайчак (2005) предполагаемый что каждый многогранный граф (а 3-вершинно-связанный планарный граф, или эквивалентно Теорема Стейница график выпуклый многогранник ) имеет жадное вложение в евклидову плоскость.[9] Используя свойства кактус графики, Лейтон и Мойтра (2010) доказал гипотезу;[8][10] жадные вложения этих графов могут быть определены кратко, используя логарифмическое количество битов на координату.[11] Однако жадные вложения, построенные в соответствии с этим доказательством, не обязательно являются планарными вложениями, поскольку они могут включать пересечения между парами ребер. За максимальные планарные графы, в котором каждая грань представляет собой треугольник, можно найти жадное плоское вложение, применив Лемма Кнастера – Куратовского – Мазуркевича. к взвешенной версии прямолинейное вложение алгоритм Шнайдера.[12][13] В сильная гипотеза Пападимитриу – Ратайчака, что каждый многогранный граф имеет плоское жадное вложение, в котором все грани выпуклые, остается недоказанным.[14]

Графики блочного диска

Сети беспроводных датчиков, которые являются целью алгоритмов жадного внедрения, часто моделируются как графы единичного диска, графы, в которых каждый узел представлен как единичный диск и каждое ребро соответствует паре дисков с непустым пересечением. Для этого специального класса графов можно найти сжатые жадные вложения в евклидово пространство полилогарифмической размерности с дополнительным свойством, заключающимся в том, что расстояния в графе точно аппроксимируются расстояниями во встраивании, так что пути, по которым идет жадная маршрутизация, являются короткая.[15]

Рекомендации

  1. ^ Рао, Анант; Ратнасами, Сильвия; Пападимитриу, Христос Х.; Шенкер, Скотт; Стойка, Ион (2003), «Географическая маршрутизация без информации о местоположении», Proc. Девятый ACM по мобильным вычислениям и сетям (MobiCom), стр. 96–108, Дои:10.1145/938985.938996.
  2. ^ а б Пападимитриу, Христос Х.; Ратайчак, Дэвид (2005), «Об одной гипотезе, связанной с геометрической маршрутизацией», Теоретическая информатика, 344 (1): 3–14, Дои:10.1016 / j.tcs.2005.06.022, МИСТЕР  2178923.
  3. ^ а б Эппштейн, Д.; Гудрич, М. Т. (2011), «Краткая жадная геометрическая трассировка с использованием гиперболической геометрии», Транзакции IEEE на компьютерах, 60 (11): 1571–1580, Дои:10.1109 / TC.2010.257.
  4. ^ а б Клейнберг, Р. (2007), «Географическая маршрутизация с использованием гиперболического пространства», Proc. 26-я Международная конференция IEEE по компьютерным коммуникациям (ИНФОКОМ 2007), стр. 1902–1909, Дои:10.1109 / INFCOM.2007.221.
  5. ^ Цао, Лэй; Стрельцов, А .; Сан, Дж. З. (2009), "О краткости геометрической жадной маршрутизации в евклидовой плоскости", 10-й Международный симпозиум по распространенным системам, алгоритмам и сетям (ISPAN 2009), стр. 326–331, Дои:10.1109 / I-SPAN.2009.20.
  6. ^ Анджелини, Патрицио; Ди Баттиста, Джузеппе; Фрати, Фабрицио (2010), «Лаконичные жадные рисунки не всегда существуют», Графический рисунок: 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22-25 сентября 2009 г., Исправленные статьи, Конспект лекций по информатике, 5849, стр. 171–182, Дои:10.1007/978-3-642-11805-0_17.
  7. ^ Нёлленбург, Мартин; Пруткин, Роман (2013), «Евклидовы жадные рисунки деревьев», Proc. 21-й Европейский симпозиум по алгоритмам (ESA 2013), arXiv:1306.5224, Bibcode:2013arXiv1306.5224N.
  8. ^ а б Лейтон, Том; Мойтра, Анкур (2010), "Некоторые результаты о жадных вложениях в метрические пространства", Дискретная и вычислительная геометрия, 44 (3): 686–705, Дои:10.1007 / s00454-009-9227-6, МИСТЕР  2679063.
  9. ^ Пападимитриу, Христос Х.; Ратайчак, Дэвид (2005), «Об одной гипотезе, связанной с геометрической маршрутизацией», Теоретическая информатика, 344 (1): 3–14, Дои:10.1016 / j.tcs.2005.06.022, МИСТЕР  2178923.
  10. ^ Смотрите также Анджелини, Патрицио; Фрати, Фабрицио; Грилли, Лука (2010), "Алгоритм построения жадных чертежей триангуляций", Журнал графических алгоритмов и приложений, 14 (1): 19–51, Дои:10.7155 / jgaa.00197, МИСТЕР  2595019.
  11. ^ Гудрич, Майкл Т.; Страш, Даррен (2009), «Краткая жадная геометрическая трассировка в евклидовой плоскости», Алгоритмы и вычисления: 20-й Международный симпозиум, ISAAC 2009, Гонолулу, Гавайи, США, 16-18 декабря 2009 г., Труды, Конспект лекций по информатике, 5878, Берлин: Springer, стр. 781–791, arXiv:0812.3893, Дои:10.1007/978-3-642-10631-6_79, МИСТЕР  2792775.
  12. ^ Шнайдер, Вальтер (1990), "Вложение плоских графов в сетку", Proc. 1-й симпозиум ACM / SIAM по дискретным алгоритмам (SODA), стр. 138–148.
  13. ^ Дхандапани, Рагхаван (2010), «Жадные рисунки триангуляций», Дискретная и вычислительная геометрия, 43 (2): 375–392, Дои:10.1007 / s00454-009-9235-6, МИСТЕР  2579703. Смотрите также
  14. ^ Нёлленбург, Мартин; Пруткин, Роман; Руттер, Игнац (2016), «О самоподближающихся и растущих хордовых чертежах трехсвязных плоских графов», Журнал вычислительной геометрии, 7 (1): 47–69, arXiv:1409.0315, Дои:10.20382 / jocg.v7i1a3, МИСТЕР  3463906.
  15. ^ Flury, R .; Pemmaraju, S.V .; Ваттенхофер, Р. (2009), «Жадная трассировка с ограниченным растяжением», IEEE INFOCOM 2009, стр. 1737–1745, Дои:10.1109 / INFCOM.2009.5062093.