An optimal algorithm for the minimum disc cover problem

Min Te Sun*, Tsi-Ui Ik, Chuan Kai Yang, Ten Hwang Lai

*Corresponding author for this work

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

The minimum disc cover can be used to construct a dominating set on the fly for energy-efficient communications in mobile ad hoc networks, but the approach used to compute the minimum disc cover proposed in previous studies is computationally relatively expensive. In this paper, we show that the disc cover problem is in fact a special case of the general α-hull problem. In spite of being a special case, the disc cover problem is not easier than the general α-hull problem. In addition to applying the existing α-hull algorithm to solve the disc cover problem, we present a simple, yet optimal divide-and-conquer algorithm that constructs the minimum disc cover for arbitrary cases, including those degenerate cases where the α-hull approach would fail.

Original languageEnglish
Pages (from-to)58-71
Number of pages14
JournalAlgorithmica (New York)
Volume50
Issue number1
DOIs
StatePublished - 1 Jan 2008

Keywords

  • Applications in ad hoc networks
  • Minimum disc cover
  • Optimal algorithms
  • α-hull

Fingerprint Dive into the research topics of 'An optimal algorithm for the minimum disc cover problem'. Together they form a unique fingerprint.

Cite this