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).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 [4], almost closing the gap with the lower bound of 6 [12].

Tightening the upper bound for the Minimum Energy Broadcasting

FLAMMINI, MICHELE
2008

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).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 [4], almost closing the gap with the lower bound of 6 [12].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/561
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact