کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
417920 681592 2016 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An exact algorithm for the bottleneck 2-connected kk-Steiner network problem in LpLp planes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
An exact algorithm for the bottleneck 2-connected kk-Steiner network problem in LpLp planes
چکیده انگلیسی

We present the first exact polynomial time algorithm for constructing optimal geometric bottleneck 2-connected Steiner networks containing at most kk Steiner points, where k>2k>2 is a constant. Given a set of nn vertices embedded in an LpLp plane, the objective of the problem is to find a 2-connected network, spanning the given vertices and at most kk additional vertices, such that the length of the longest edge is minimised. In contrast to the discrete version of this problem the additional vertices may be located anywhere in the plane. The problem is motivated by the modelling of relay-augmentation for the optimisation of energy consumption in wireless ad hoc networks. Our algorithm employs Voronoi diagrams and properties of block-cut-vertex decompositions of graphs to find an optimal solution in O(nklog5k2n) steps when 1

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 201, 11 March 2016, Pages 47–69
نویسندگان
, , ,