Tighter bounds for the minimum energy broadcasting problem

A. Navarra

3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Tighter bounds for the minimum energy broadcasting problem

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2005.51,
    author={ A. Navarra},
    title={Tighter bounds for the minimum energy broadcasting problem},
    proceedings={3rd International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
    publisher={IEEE},
    proceedings_a={WIOPT},
    year={2005},
    month={4},
    keywords={},
    doi={10.1109/WIOPT.2005.51}
}

A. Navarra
Year: 2005
Tighter bounds for the minimum energy broadcasting problem
WIOPT
IEEE
DOI: 10.1109/WIOPT.2005.51

A. Navarra¹

1: Dept. of Comput. Sci., L'Aquila Univ., Italy

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).

Published: 2005-04-25
Publisher: IEEE

: http://dx.doi.org/10.1109/WIOPT.2005.51