liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
New results on the time complexity and approximation ratio of the Broadcast Incremental Power algorithm
University of Bergen.
University of Bergen.
Linköping University, The Institute of Technology. Linköping University, Department of Science and Technology, Communications and Transport Systems.
2009 (English)In: INFORMATION PROCESSING LETTERS, ISSN 0020-0190, Vol. 109, no 12, 615-619 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
Approximation algorithms, Analysis of algorithms, Wireless ad hoc network, Minimum energy broadcast
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-18149DOI: 10.1016/j.ipl.2009.02.012OAI: 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. Copyright: Elsevier Science B.V., Amsterdam. from: 2009-05-20 Created: 2009-05-08 Last updated: 2012-06-25Bibliographically approved

Open Access in DiVA

fulltext(220 kB)111 downloads
File information
File name FULLTEXT01.pdfFile size 220 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Yuan, Di
By organisation
The Institute of TechnologyCommunications and Transport Systems
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 111 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 132 hits
ReferencesLink to record
Permanent link

Direct link