Back to search

University of Victoria (Canada)

On the complexity of energy-efficient broadcasting in wireless networks

Abstract

dc:description.abstract

We examine the complexity of the minimum-energy broadcast tree problem for wire-less networks. Some versions are known to be NP-complete. We show that the Euclidean version with unlimited power levels is also NP-complete. We assume a broadcast power metric of p(r) = kra where r is the broadcast radius, and k > 0 and a > 2 are properties of the signal propagation medium. We prove NP-completeness using a reduction from the planar 3-satisfiability problem

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hollemans, Peter Francis
Advisor dc:contributor.supervisor
  • King, Valerie

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/1071

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hollemans, Peter Francis. On the complexity of energy-efficient broadcasting in wireless networks. Master of Science M.Sc. thesis, 2008. http://hdl.handle.net/1828/1071