Incrustaciones codiciosas

En computación distribuida y teoría geométrica de grafos , el incrustamiento voraz es un proceso que asigna coordenadas a los nodos de una red de telecomunicaciones para permitir el enrutamiento geográfico voraz en la distribución de mensajes dentro de la red. Si bien se ha propuesto el incrustamiento voraz para su uso en redes de sensores inalámbricas , donde los nodos ya tienen posiciones en el espacio físico, estas posiciones existentes pueden diferir de las posiciones que les asigna el incrustamiento voraz, que en algunos casos pueden ser puntos en un espacio virtual de mayor dimensión o en una geometría no euclidiana . En este sentido, el incrustamiento voraz puede considerarse una forma de dibujo de grafos , en la que un grafo abstracto (la red de comunicaciones) se incrusta en un espacio geométrico.

La idea de realizar el enrutamiento geográfico utilizando coordenadas en un espacio virtual, en lugar de utilizar coordenadas físicas, se debe a Rao et al. ^{[ 1 ]} Desarrollos posteriores han demostrado que cada red tiene una incrustación voraz con coordenadas de vértice sucintas en el plano hiperbólico , que ciertos grafos, incluidos los grafos poliédricos, tienen incrustaciones voraces en el plano euclidiano , y que los grafos de disco unitario tienen incrustaciones voraces en espacios euclidianos de dimensiones moderadas con factores de estiramiento bajos.

En el enrutamiento voraz, un mensaje desde un nodo fuente s a un nodo destino t viaja a su destino mediante una secuencia de pasos a través de nodos intermedios, cada uno de los cuales pasa el mensaje a un nodo vecino más cercano a t . Si el mensaje llega a un nodo intermedio x que no tiene un vecino más cercano a t , entonces no puede avanzar y el proceso de enrutamiento voraz falla. Una incrustación voraz es una incrustación del grafo dado con la propiedad de que un fallo de este tipo es imposible. Por lo tanto, se puede caracterizar como una incrustación del grafo con la propiedad de que para cada par de nodos x y t , existe un vecino y de x tal que d ( x , t )  > d ( y , t ), donde d denota la distancia en el espacio incrustado. ^{[ 2 ]} 

No todos los grafos tienen una incrustación voraz en el plano euclidiano ; un contraejemplo simple lo da la estrella K _1,6 , un árbol con un nodo interno y seis hojas. ^{[ 2 ]} Siempre que este grafo se incruste en el plano, dos de sus hojas deben formar un ángulo de 60 grados o menos, de lo cual se deduce que al menos una de estas dos hojas no tiene un vecino que esté más cerca de la otra hoja.

En espacios euclidianos de dimensiones superiores, más grafos pueden tener incrustaciones voraces; por ejemplo, K _1,6 tiene una incrustación voraz en un espacio euclidiano tridimensional, en el que el nodo interno de la estrella está en el origen y las hojas están a una distancia unitaria a lo largo de cada eje de coordenadas. Sin embargo, para cada espacio euclidiano de dimensión fija, existen grafos que no pueden incrustarse de forma voraz: siempre que el número n sea mayor que el número de contacto del espacio, el grafo K _{1, n} no tiene incrustación voraz. ^{[ 3 ]}

A diferencia del caso del plano euclidiano, toda red tiene una incrustación voraz en el plano hiperbólico . La demostración original de este resultado, realizada por Robert Kleinberg , requería que las posiciones de los nodos se especificaran con alta precisión, ^{[ 4 ]} pero posteriormente se demostró que, mediante una descomposición de caminos pesada de un árbol de expansión de la red, es posible representar cada nodo de forma concisa, utilizando solo un número logarítmico de bits por punto. ^{[ 3 ]} En contraste, existen grafos que tienen incrustaciones voraces en el plano euclidiano, pero para los cuales cualquier incrustación de este tipo requiere un número polinomial de bits para las coordenadas cartesianas de cada punto. ^{[ 5 ] [ 6 ]}