標題: An optimal algorithm for the minimum disc cover problem
作者: Sun, Min-Te
Yi, Chih-Wei
Yang, Chuan-Kai
Lai, Ten-Hwang
資訊工程學系
Department of Computer Science
關鍵字: minimum disc cover;alpha-hull;optimal algorithms;applications in ad hoc networks
公開日期: 1-Jan-2008
摘要: 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 alpha-hull problem. In spite of being a special case, the disc cover problem is not easier than the general alpha-hull problem. In addition to applying the existing alpha-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 alpha-hull approach would fail.
URI: http://dx.doi.org/10.1007/s00453-007-9043-4
http://hdl.handle.net/11536/9961
ISSN: 0178-4617
DOI: 10.1007/s00453-007-9043-4
期刊: ALGORITHMICA
Volume: 50
Issue: 1
起始頁: 58
結束頁: 71
Appears in Collections:Articles


Files in This Item:

  1. 000251647800002.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.