New results on the time complexity and approximation ratio of the Broadcast Incremental Power algorithm
2009 (English)In: INFORMATION PROCESSING LETTERS, ISSN 0020-0190, Vol. 109, no 12, 615-619 p.Article in journal (Refereed) Published
The Broadcast Incremental Power (BIP) algorithm is the most frequently cited method for the minimum energy broadcast routing problem. A recent survey concluded that BIP has O(|V|(3)) time complexity, and that its approximation ratio is at least 4.33. We strengthen these results to O(|V|(2)) and 4.598, respectively.
Place, publisher, year, edition, pages
2009. Vol. 109, no 12, 615-619 p.
Approximation algorithms, Analysis of algorithms, Wireless ad hoc network, Minimum energy broadcast
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-18149DOI: 10.1016/j.ipl.2009.02.012OAI: oai:DiVA.org:liu-18149DiVA: diva2:216488
Original Publication: Joanna Bauer, Dag Haugland and Di Yuan , New results on the time complexity and approximation ratio of the Broadcast Incremental Power algorithm, 2009, INFORMATION PROCESSING LETTERS, (109), 12, 615-619. http://dx.doi.org/10.1016/j.ipl.2009.02.012 Copyright: Elsevier Science B.V., Amsterdam. http://www.elsevier.com/2009-05-202009-05-082012-06-25Bibliographically approved