貪欲埋め込み

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

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

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

すべてのグラフがユークリッド平面に貪欲に埋め込まれるわけではありません。簡単な反例として、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]