Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.18 No.2, pp.311-331 (March 2002)

Bottleneck Domination and Bottleneck Independent
Domination on Graph*

William Chung-Kune Yen
Department of Graphic Communications and Technology
Shih Hsin University
Taipei, 116 Taiwan
E-mail: ckyen001@ms7.hinet.net

In this paper, the bottleneck dominating set problem and one of its variants, the bottleneck independent dominating set problem, are considered. Let G(V, E, W) denote a graph with n-vertex-set V and m-edge-set E, where each vertex v is associated with a real cost W(v). Given any subset V? of V, the bottleneck cost of V? is defined as max{W(x) ? x ? V?}. The major task involves identifying a dominating set / independent dominating set of G such that their bottleneck costs are minimized. This paper first proposes an O(nlogn + m) time algorithm for solving the Bottleneck Dominating Set problem on weighted general graphs using the binary search technique. Second, an O(n) time algorithm is designed for the problem on weighted trees. Then, we show that the situation is greatly different when the Bottleneck Independent Dominating Set problem (the BIDS problem) is considered. This paper proves that the BIDS problem is NP-hard on planar graphs and presents a linear-time optimal algorithm for the BIDS problem on weighted interval graphs.

Keywords: bottleneck cost, dominating set, independent dominating set, tree, planar graph, interval graph

Full Text () Retrieve PDF document (200203_08.pdf)

Received May 25, 2000; revised November 10, 2000; accepted January 9, 2001.
Communicated by Jang-Ping Sheu.
*This research was supported by National Science Council, ROC, under contract number NSC-89-2213-E-159-001.