کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426110 685996 2012 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient algorithms for the conditional covering problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Efficient algorithms for the conditional covering problem
چکیده انگلیسی

We consider the conditional covering problem in an undirected network, in which each vertex represents a demand point that must be covered by a facility as well as a potential facility site. Each facility can cover all vertices within a given coverage radius, except the vertex at which the facility is located. The objective is to locate facilities to cover all vertices such that the total facility location cost is minimized. In this paper, new upper bounds are proposed for the conditional covering problem on paths, cycles, extended stars, and trees. In particular, we provide an O(nlogn)-time algorithm for paths, an O(n2logn)-time algorithm for cycles, an O(n1.5logn)-time algorithm for extended stars, and an O(n3)O(n3)-time algorithm for trees. Our algorithms for paths, extended stars, and trees improve the previous upper bounds from O(n2)O(n2), O(n2)O(n2), and O(n4)O(n4), respectively.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 219, October 2012, Pages 39–57
نویسندگان
, , , , , ,