Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

New results on the time complexity and approximation ratio of the Broadcast Incremental Power algorithm

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • بيانات النشر:
      Linköpings universitet, Tekniska högskolan
      Linköpings universitet, Kommunikations- och transportsystem
      University of Bergen
    • الموضوع:
      2009
    • Collection:
      Linköping University Electronic Press (LiU E-Press)
    • نبذة مختصرة :
      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. ; 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/
    • File Description:
      application/pdf
    • Relation:
      INFORMATION PROCESSING LETTERS, 0020-0190, 2009, 109:12, s. 615-619; http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-18149
    • الرقم المعرف:
      10.1016/j.ipl.2009.02.012
    • الدخول الالكتروني :
      http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-18149
      https://doi.org/10.1016/j.ipl.2009.02.012
    • Rights:
      info:eu-repo/semantics/openAccess
    • الرقم المعرف:
      edsbas.73872BF3