Greedy embedding とは

分散コンピューティングおよび幾何学グラフ理論では、欲張り埋め込みは、ネットワーク内のメッセージをルーティングするために貪欲な地理的ルーティングを使用できるように、電気通信ネットワークのノードに座標を割り当てるプロセスである。欲張り埋め込みは、ノードが既に物理空間内の位置を有する無線センサネットワークにおいて使用するために提案されているが、これらの既存の位置は、貪欲な埋め込みによって与えられた位置とは異なる場合があり、場合によっては仮想空間より高い次元の、または非ユークリッドの幾何学的形状である。この意味では、欲張り埋め込みは、抽象的なグラフ(通信ネットワーク)が幾何学的空間に埋め込まれた一種のグラフ描画と見ることができる。
物理座標を使用する代わりに、仮想空間内の座標を使用して地理的ルーティングを実行するという考え方は、Raoらによるものである。その後の発展は、すべてのネットワークが双曲線平面内の簡潔な頂点座標を持つ貪欲な埋め込みを有し、多面体グラフを含む特定のグラフがユークリッド平面に貪欲な埋め込みを有し、その単位ディスクグラフが、低いストレッチファクター。