Institute of Theoretical Informatics, Algorithmics II

An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication

  • Author(s):

    Dennis Schieferdecker

  • Source:

    Dissertation (2014)

    Institut für Theoretische Informatik

  • Date: July 2014
  • Dissertation

    This thesis focuses on scalability issues of diverse problems on sensor networks and present efficient solutions. First, we show that it is NP-hard to find optimal activation schedules for monitoring areas and provide an EPTAS algorithm. Second, we present a distributed algorithm for the detection of network boundaries that only requires local connectivy information. Finally, we introduce an FPTAS for computing shortest paths and describe an algorithm for determining alternative routes.