Đang chuẩn bị liên kết để tải về tài liệu:
Topology Control in Wireless Ad Hoc and Sensor Networks phần 5

bằng tổng của các lĩnh vực A1 và A2 (chúng tôi giả sử R = [0, 1] 2). nghỉ ngơi tại một waypoint đó là gần với biên giới của R (xem Hình 5.1). Kể từ khi waypoint tiếp theo là chọn thống nhất một cách ngẫu nhiên trong R, rất có khả năng rằng các quỹ đạo u nút kết nối với waypoint tiếp theo của nó sẽ vượt qua trung tâm của R. | 84 THE RANGE ASSIGNMENT PROBLEM least yk the increase for every YZ-component is bounded by 2 k e 2 - yk 2 k2. Considering that k m 1 we have c RA c RÃab y2k2 k e 2 m 1 2 k e 2 yk 2 k2 0 by inequality 7.1 . This ends the proof of the lemma. Consider a planar cubic graph G and a planar orthogonal drawing D G of G and let 2h be the number of nodes added in the second step of the construction. Assign to every node in G and in D G a weight equal to its degree. The following lemma relates the cost of a vertex cover for G with that of a vertex cover for D G . Lemma 7.4.5 Let G be a planar cubic graph D G a planar orthogonal drawing of G and let 2h be the number of nodes added in the construction. Assign to every node in G and in D G a weight equal to its degree. Then G has a vertex cover of cost k if and only if D G has a vertex cover of cost k 2h. Proof. The proof follows easily from Lemma 3.1 of Kirousis et al. 2000 and by observing that every node added in the construction of D G has degree 2. We are now ready to prove that SRA in two-dimensional networks is NP-hard. Theorem 7.4.6 Solving the SRA problem in two- and three-dimensional networks is NP-hard. Proof. We show a polynomial time reduction from MinWeightedVertexCover for planar cubic graphs. Let G be any planar cubic graph and let D G V E be a straight-line planar orthogonal drawing of G. By Lemma 7.4.5 the problems of determining a vertex cover of minimum weight on D G and on G are equivalent and hence MinWeightedVertexCover on D G is NP-hard. Consider now the set of two-dimensional points S G obtained by constructing gadgets on every edge of D G as described above. In Clementi et al. 1999 it is proved that for any D G it is possible to derive S G in polynomial time and that points in the gadgets satisfy condition a . e for positive constants y k k e such that k e k and yk 2 m 1 k e 2 k2 k e 2 -1 k e 2 k2 k e 2. m It can be seen that the same choice of y k k and e enables points in the gadgets to have the .