Nodes are located in the Euclidean plane and are assumed to have identical (unit) transmission radii. If the embedding is allowed to reside in higher dimensional space, we obtain improved results: a quality-2 embedding in constant dimensional Euclidean space. One prominent application of unit disk graphs can be found in the eld of wireless networking, where a unit disk graph represents an idealizedmulti-hop radio network. Such a clique partition also represents our key technical contribution.
Thus, not only is our algorithm an improvement, it also bypasses the standard and costly technique of solving a linear program with exponentially many “spreading constraints.” As a side effect of our construction, we get the first constant-factor approximation to the minimum clique partition problem for UDGs expressed in general form. If the disks do not overlap, it is also a unit coin graph or penny graph. Each edge of G(P) connects points pand p0from P whenever kp p0k 1, where kkdenotes the Euclidean norm. top A unit disk graph is the intersection graph of a family of unit disks in the plane. Thus, we will drop the use of disks and just refer to the graph G(P) defined by a set P of npoints in the plane. In this article, we give a combinatorial algorithm that achieves an O(log 3 n) quality realization of an n-vertex UDG expressed in general form. A unit disk graph is uniquely defined by the centers of the disks. gave a O(log 3.5 n (loglog n) 1/2}) quality realization that requires solving a linear program with exponentially many constraints by using the ellipsoid algorithm. Thus, an optimum quality realization has quality between 1/2 and 1. The problem is to construct an embedding of the graph in low-dimensional Euclidean space so that the ratio of the length of the longest edge under the embedding to the length of the shortest non-edge under the embedding is as small as possible the measure is known as the quality of the realization. We consider the problem of finding a realization of an n-vertex unit disk graph (UDG) expressed in general form, say, as an adjacency matrix.
0 kommentar(er)
