Notice that both OrdY aoGG and SY aoGG are degree-bounded planar
power spanners, but they are not length spanners. However, BPS(V ) is a
degree-bounded planar length spanner. The summary of properties of all spanners
reviewed is given in Table 1.
127
Yu Wang
Table 1. Summary of the geometric spanners
Power-Spanner Length-Spanner Bounded-Degree Planar Built-Locally
RNG no no no yes yes
GG yes no no yes yes
Del yes yes no yes no
LDel yes yes no yes yes
RDG yes yes no yes yes
Y G yes yes no no yes
Y G?ยค yes yes yes no yes
Y Y yes open yes no yes
Y S no no yes no yes
BPS yes yes yes yes yes
OY AOGG yes no yes yes yes
SY AOGG yes no yes yes yes
3 Geometrical Low-Weight Structures
The power stretch factor we previously discussed is defined for unicasting
communications. However, in practice, we also have to consider broadcast or
multicast communications. Wan et al [47] showed that the minimum energy
cost of broadcasting or multicasting is related to the total energy cost of all
links in the Euclidean minimum spanning tree MST. The minimum spanning
tree of G, denoted by MST(G), is the tree belong to E that connects all
nodes and whose total edge length is minimized. MST(G) is obviously one of
the sparsest connected subgraphs. Wan et al [47] proved that a broadcasting
method based on the Euclidean minimum spanning tree rooted at the sender
uses energy no more than 12 times the minimum energy cost of any broadcasting
scheme.
Pages:
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222