貪欲埋め込み

分散コンピューティングと幾何学的グラフ理論において、貪欲埋め込みとは、通信ネットワークのノードに座標を割り当て、貪欲な地理的ルーティングを使用してネットワーク内のメッセージをルーティングできるようにするプロセスです。貪欲埋め込みは、ノードがすでに物理空間内に位置を持っている無線センサーネットワークでの使用が提案されていますが、これらの既存の位置は、貪欲埋め込みによって割り当てられた位置と異なる場合があり、場合によっては、より高次元の仮想空間内または非ユークリッド幾何学内の点になることがあります。この意味で、貪欲埋め込みは、抽象的なグラフ（通信ネットワーク）が幾何学的空間に埋め込まれるグラフ描画の一種と見なすことができます。

物理的な座標ではなく、仮想空間の座標を使用して地理的なルーティングを実行するというアイデアは、Rao らによるものです。[ 1 ]その後の開発により、すべてのネットワークは双曲面内に簡潔な頂点座標を持つ貪欲埋め込みを持ち、多面体グラフを含む特定のグラフはユークリッド平面内に貪欲埋め込みを持ち、単位ディスクグラフはストレッチ係数が低い中程度の次元のユークリッド空間に貪欲埋め込みを持つことが示されました。

定義

貪欲ルーティングでは、送信元ノードsから宛先ノードtへのメッセージは、中間ノードを経由する一連のステップによって宛先に送られ、各中間ノードはメッセージをtにより近い隣接ノードに渡します。メッセージがtにより近い隣接ノードを持たない中間ノードxに到達した場合、メッセージは先に進めず、貪欲ルーティングプロセスは失敗します。貪欲埋め込みとは、この種の失敗はあり得ないという特性を持つグラフの埋め込みです。したがって、これは、2つのノードxとtごとに、 d ( x , t ) > d ( y , t ) となるようなxの隣接ノードyが存在するという特性を持つグラフの埋め込みとして特徴付けることができます。ここで、d は埋め込み空間における距離を表します。[ 2 ]

貪欲埋め込みのないグラフ

K 1,6 、ユークリッド平面に貪欲埋め込みのないグラフ

すべてのグラフがユークリッド平面に貪欲に埋め込まれるわけではない。簡単な反例として、内部ノードが1つで葉が6つある星型グラフK 1,6がある。 [ 2 ]このグラフが平面に埋め込まれるときは、必ずその葉のうちの2つが60度以下の角度を形成する必要がある。したがって、これら2つの葉のうち少なくとも1つには、もう1つの葉に近い隣接葉がないことになる。

高次元ユークリッド空間では、より多くのグラフが貪欲埋め込みを持つ可能性がある。例えば、K 1,6は3次元ユークリッド空間への貪欲埋め込みを持つ。この空間では、星の内部ノードは原点にあり、葉は各座標軸に沿って単位距離離れている。しかし、固定次元のユークリッド空間には、貪欲に埋め込むことができないグラフも存在する。つまり、nが空間のキス数よりも大きい場合、グラフK 1, nは貪欲埋め込みを持たない。[ 3 ]

双曲型埋め込みと簡潔型埋め込み

ユークリッド平面の場合とは異なり、すべてのネットワークは双曲平面への貪欲埋め込みを持つ。この結果の最初の証明はロバート・クラインバーグによるもので、ノードの位置を高精度で指定する必要がありましたが[ 4 ] 、その後、ネットワークの全域木の重パス分解を用いることで、各ノードを簡潔に表現し、点あたり対数ビット数のみで表現できることが示されました[ 3 ] 。対照的に、ユークリッド平面に貪欲埋め込みを持つグラフも存在しますが、そのような埋め込みには各点の直交座標に多項式数のビット数が必要です[ 5 ] [ 6 ] 。

グラフの特別なクラス

木々

ユークリッド平面への貪欲埋め込みを許容する木のクラスは完全に特徴付けられており、木の貪欲埋め込みは、それが存在する場合には線形時間で見つけることができる。[ 7 ]

より一般的なグラフでは、Kleinberg [ 4 ]のような貪欲埋め込みアルゴリズムがいくつかあり、まず与えられたグラフの全域木を求め、次にその全域木の貪欲埋め込みを構築する。その結果は必然的にグラフ全体の貪欲埋め込みとなる。しかし、ユークリッド平面上に貪欲埋め込みを持つグラフが存在するものの、全域木には貪欲埋め込みを持たないグラフも存在する。[ 8 ]

平面グラフ

数学における未解決問題
すべての多面体グラフには凸面を持つ平面貪欲埋め込みがありますか?
数学におけるさらなる未解決問題

Papadimitriou & Ratajczak (2005) は、あらゆる多面体グラフ( 3 頂点接続の平面グラフ、またはSteinitz の定理により凸多面体のグラフと同等) はユークリッド平面への貪欲埋め込みを持つと予想しました。 [ 2 ]サボテングラフの特性を利用して、Leighton & Moitra (2010) はこの予想を証明しました。[ 8 ] [ 9 ]これらのグラフの貪欲埋め込みは、座標ごとに対数的なビット数で簡潔に定義できます。[ 10 ] ただし、この証明に従って構築された貪欲埋め込みは、エッジのペア間の交差を含む場合があるため、必ずしも平面埋め込みではありません。すべての面が三角形である最大平面グラフの場合、貪欲平面埋め込みは、シュナイダーの直線埋め込みアルゴリズムの重み付きバージョンにクナスター・クラトフスキー・マズルキエヴィチの補題を適用することによって見つけることができます。 [ 11 ] [ 12 ]すべての多面体グラフには、すべての面が凸である平面貪欲埋め込みが存在するという強いパパディミトリウ・ラタジチャク予想は、まだ証明されていません。[ 13 ]

単位円グラフ

貪欲埋め込みアルゴリズムの対象となる無線センサーネットワークは、単位円グラフとしてモデル化されることが多い。単位円グラフとは、各ノードが単位円として表現され、各辺が空でない交差を持つ円のペアに対応するグラフである。この特殊なグラフクラスでは、多重対数次元のユークリッド空間への簡潔な貪欲埋め込みを見つけることが可能であり、さらにグラフ内の距離が埋め込み内の距離によって正確に近似されるため、貪欲ルーティングが辿る経路が短くなるという特性がある。[ 14 ]

参考文献

  1. ^ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H .; Shenker, Scott ; Stoica, Ion (2003)、「位置情報なしの地理ルーティング」、Proc. 9th ACM Mobile Computing and Networking (MobiCom)、pp.  96– 108、doi : 10.1145/938985.938996、ISBN 1-58113-753-2、S2CID  8374920。
  2. ^ a b cパパディミトリウ、クリストス・H. ; ラタジチャク、デイヴィッド (2005)、「幾何学的ルーティングに関する予想について」、理論計算機科学、344 (1): 3– 14、doi : 10.1016/j.tcs.2005.06.022、MR 2178923 。
  3. ^ a b Eppstein, D. ; Goodrich, MT (2011)、「双曲幾何学を用いた簡潔な貪欲幾何学ルーティング」、IEEE Transactions on Computers、60 (11): 1571– 1580、Bibcode : 2011ITCmp..60.1571E、doi : 10.1109/TC.2010.257、S2CID 40368995 。
  4. ^ a b Kleinberg, R. (2007)、「双曲空間を用いた地理ルーティング」、Proc. 26th IEEE International Conference on Computer Communications (INFOCOM 2007)、pp.  1902– 1909、doi : 10.1109/INFCOM.2007.221、ISBN 978-1-4244-1047-7、S2CID  11845175。
  5. ^ Cao, Lei; Strelzoff, A.; Sun, JZ (2009)「ユークリッド平面における幾何学的貪欲ルーティングの簡潔性について」、第10回国際パーベイシブシステム、アルゴリズム、ネットワークシンポジウム (ISPAN 2009)、pp.  326– 331、doi : 10.1109/I-SPAN.2009.20、ISBN 978-1-4244-5403-7、S2CID  6513298。
  6. ^ Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio (2010)、「簡潔な貪欲描画は常に存在するわけではない」、Graph Drawing: 17th International Symposium, GD 2009、シカゴ、イリノイ州、米国、2009年9月22日～25日、改訂論文、Lecture Notes in Computer Science、vol. 5849、pp.  171– 182、doi : 10.1007/978-3-642-11805-0_17、ISBN 978-3-642-11804-3。
  7. ^ Nöllenburg, Martin; Prutkin, Roman (2013), "Euclidean greedy drawing of trees", Proc. 21st European Symposium on Algorithms (ESA 2013) , arXiv : 1306.5224 , Bibcode : 2013arXiv1306.5224N。
  8. ^ a bレイトン、トム; モイトラ、アンクル (2010)、「距離空間における貪欲埋め込みに関するいくつかの結果」、離散および計算幾何学、44 (3): 686– 705、doi : 10.1007/s00454-009-9227-6、hdl : 1721.1/80843、MR 2679063 。
  9. ^ Angelini, Patrizio; Frati, Fabrizio; Grilli, Luca (2010)、「三角形分割の貪欲描画を構築するアルゴリズム」、Journal of Graph Algorithms and Applications、14 (1): 19– 51、doi : 10.7155/jgaa.00197、MR 2595019 。
  10. ^ Goodrich, Michael T. ; Strash, Darren (2009)、「ユークリッド平面における簡潔な貪欲幾何学的ルーティング」、アルゴリズムと計算：第20回国際シンポジウム、ISAAC 2009、ホノルル、ハワイ、米国、2009年12月16日～18日、議事録、Lecture Notes in Computer Science、vol. 5878、ベルリン：Springer、pp.  781– 791、arXiv：0812.3893、doi：10.1007/978-3-642-10631-6_79、ISBN 978-3-642-10630-9、MR  2792775、S2CID  15026956。
  11. ^ Schnyder, Walter (1990)、「グリッドへの平面グラフの埋め込み」、第1回ACM/SIAM離散アルゴリズムシンポジウム(SODA)、pp.  138– 148。
  12. ^ Dhandapani, Raghavan (2010)、「三角測量の貪欲描画」、離散幾何学と計算幾何学、43 (2): 375– 392、doi : 10.1007/s00454-009-9235-6、MR 2579703、S2CID 11617189  . 参照
  13. ^ Nöllenburg, Martin; Prutkin, Roman; Rutter, Ignaz (2016)「3連結平面グラフの自己接近および増加弦描画について」Journal of Computational Geometry , 7 (1): 47– 69, arXiv : 1409.0315 , doi : 10.20382/jocg.v7i1a3 , MR 3463906 , S2CID 1500695  。
  14. ^ Flury, R.; Pemmaraju, SV; Wattenhofer, R. (2009)「制限付きストレッチによる貪欲ルーティング」、IEEE Infocom 2009、pp.  1737– 1745、doi : 10.1109/INFCOM.2009.5062093、ISBN 978-1-4244-3512-8、S2CID  1881560。
「 https://en.wikipedia.org/w/index.php?title=Greedy_embedding&oldid=1335683255」より取得