کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
396141 | 666293 | 2007 | 13 صفحه PDF | دانلود رایگان |

Given the trapezoid diagram, the problem of finding the minimum cardinality connected dominating set in trapezoid graphs was solved in O(m+n)O(m+n) time [Y.D. Liang, Steiner set and connected domination in trapezoid graphs, Inform. Process. Lett. 56 (2) (1995) 101–108]. Köhler [E. Köhler, Connected domination and dominating clique in trapezoid graphs, Discr. Appl. Math. 99 (2000) 91–110] recently improved this result to O(n)O(n) time. For the (vertex) weighted case, the problem of finding the minimum weighted connected dominating set in trapezoid graphs can be solved in O(m+nlogn)O(m+nlogn) time [Anand Srinivasan, M.S. Chang, K. Madhukar, C. Pandu Rangan, Efficient algorithms for the weighted domination problems on trapezoid graphs, Manuscript, 1996]. Herein n (m) denotes the number of vertices (edges) of the trapezoid graph.In this paper, we show a different approach for the problem of finding the minimum cardinality connected dominating set in trapezoid graphs using O(n)O(n) time. For finding the minimum weighted connected dominating set, we show the problem can be solved in O(nloglogn)O(nloglogn) time.
Journal: Information Sciences - Volume 177, Issue 12, 15 June 2007, Pages 2405–2417