The bottleneck independent domination on the classes of bipartite graphs and block graphs

Let <f>G(V,E,W)</f> denote a graph with vertex-set <f>V</f> and edge-set <f>E</f>, and each vertex <f>v</f> is associated with a cost <f>W(v)</f>. For any set <f>V′⊆V</f>, the bottleneck cost of <f>V′</f> is defined as <f>max{W(x)|x∈V′}</f>. This paper considers the bottleneck independent dominating set problem (the BIDS problem) which determines an independent dominating set of <f>G</f> such that its bottleneck cost is minimized.This paper studies the problem on the classes of bipartite graphs and block graphs. This paper first proves that the problem is NP-hard on chordal-bipartite graphs. Second, a linear-time algorithm on convex-bipartite graphs is proposed. Next, a linear-time algorithm on trees is designed. Then, we generalize the algorithmic result to block graphs. All algorithms are designed by the dynamic programming strategy. [Copyright &y& Elsevier]