کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474245 | 698856 | 2007 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved algorithm for the p-center problem on interval graphs with unit lengths
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An improved algorithm for the p-center problem on interval graphs with unit lengths An improved algorithm for the p-center problem on interval graphs with unit lengths](/preview/png/474245.png)
چکیده انگلیسی
The p-center problem is to locate p facilities in a network of n demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O(n)O(n) time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O(pn)O(pn).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 34, Issue 8, August 2007, Pages 2215–2222
Journal: Computers & Operations Research - Volume 34, Issue 8, August 2007, Pages 2215–2222
نویسندگان
T.C.E. Cheng, Liying Kang, C.T. Ng,