In this paper we present a new upper bound on the approximation ratio of the minimum spanning tree heuristic for the basic problem on ad-hoc networks given by the minimum-energy broadcast routing (MEBR) problem. We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound (M. Flammini et al., 2004).
Tighter Bounds for the Minimum Energy Broadcasting problem
NAVARRA, Alfredo
2005
Abstract
In this paper we present a new upper bound on the approximation ratio of the minimum spanning tree heuristic for the basic problem on ad-hoc networks given by the minimum-energy broadcast routing (MEBR) problem. We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound (M. Flammini et al., 2004).File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
