کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414180 680823 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Survivable minimum bottleneck networks
ترجمه فارسی عنوان
شبکه های حداقل تنگنا قابل تحمل
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• First polynomial-time algorithm for the survivable bottleneck Steiner network problem in Minkowski planes.
• Algorithm works for a very general definition of survivability and in most “nicely” defined norms.
• The algorithm depends on a novel use of oriented Dirichlet cell partitions.
• Running time is O(n2k+3log⁡n)O(n2k+3log⁡n) in the Euclidean and rectilinear planes.

We show that the survivable bottleneck Steiner tree problem in normed planes can be solved in polynomial time when the number of Steiner points is constant. This is a fundamental problem in wireless ad-hoc network design where the objective is to design networks with efficient routing topologies. Our result holds for a general definition of survivability and for any norm whose ball is specified by a piecewise algebraic curve of bounded degree and with a bounded number of pieces. In particular, under the Euclidean and rectilinear norms our algorithm constructs an optimal solution in O(n2k+3log⁡n)O(n2k+3log⁡n) steps, where n is the number of terminals and k is the number of Steiner points. Our algorithm is based on the construction of generalised Voronoi diagrams and relative neighbourhood graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 50, December 2015, Pages 17–23
نویسندگان
,