کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649756 | 1342465 | 2009 | 18 صفحه PDF | دانلود رایگان |
A dominating set DD of a graph GG is a subset of V(G)V(G) such that for every vertex v∈V(G)v∈V(G), either v∈Dv∈D or there exists a vertex u∈Du∈D that is adjacent to vv in GG. Dominating sets of small cardinality are of interest. A connected dominating set CC of a graph GG is a dominating set of GG such that the subgraph induced by the vertices of CC in GG is connected. A weakly-connected dominating set WW of a graph GG is a dominating set of GG such that the subgraph consisting of V(G)V(G) and all edges incident with vertices in WW is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs.
Journal: Discrete Mathematics - Volume 309, Issue 8, 28 April 2009, Pages 2305–2322