When □ computes a connected dominating set CD v for G v it holds that v′ ∈ CD v (since v must be dominated either by v′ or by v itself which implies for CD v to be connected that v′ must be in CD v as well). Figure 7 shows this construction for c = 1. Again, an edge between two vertices exists if and only if the Euclidean distance between two vertices is at most one. Denote by v′ the vertex opposite of v on the inner ring. For each vertex v ∈ V O we define the unit disk graph G v as follows: it consists of the vertices V I and the vertex v. Since G c is a unit disk graph an edge between two vertices exists if and only if the Euclidean distance between the vertices is at most one. We denote by V O the vertices on the outer ring. c vertices such that each of them is opposite to one vertex in V I.c vertices distributed on the inner ring.Consider the unit disk graph G c defined as follows: There are 21 Consider two circles of diameters one and three which are placed inside of each other (see Figure 7). Without loss of generality we assume that c is an integer. In the authors provide a marking process in conjunction with two dominant pruning rules in order to reduce the size of a dominating set. Gfeller and Vicari presented a distributed PTAS for dominating set with the same locality properties. However, in these algorithms the status of a vertex depends on the vertices which are up to O (log | V|) hops away from it, which is not local in our sense. proposed local approximation schemes for maximum independent set and dominating set for growth-bounded-graphs. When looking for local algorithms, Kuhn et al. However, all these algorithms are global in the sense that in order to determine whether a given vertex is in the computed set, we need knowledge of the entire graph. When restricting the case to unit disk graphs, the problems remain NP-hard, but constant ratio approximations and PTASs are known. For vertex cover there are several 2-approximation algorithms known, e.g. Apart from vertex cover they do not even admit constant ratio approximation algorithms. In general graphs all problems which we study - dominating and connected dominating set, indepen-dent set and vertex cover - are NP-hard.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |