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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:liu:diva-18149DOI: 10.1016/j.ipl.2009.02.012OAI: oai:DiVA.org:liu-18149DiVA: diva2:216488
Note
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/Available from: 2009-05-20 Created: 2009-05-08 Last updated: 2012-06-25Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full text

Authority records BETA

Yuan, Di

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: 215 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 198 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf