In this paper we show that a p(⩾2)-center location problem in general networks can be transformed to the well-known Kleeʼs measure problem (Overmars and Yap, 1991) [15]. This results in a significantly improved algorithm for the continuous case with running time O(m^pn^p/22log^∗ n logn)for p⩾3, where n is the number of vertices, m   is the number of edges, and log^∗ n denotes the iterated logarithm of n (Cormen et al., 2001) [10]. For p=2, the running time of the improved algorithm is O(m²n log ²n). The previous best result for the problem is O(m^pn^pα(n) logn)where α(n) is the inverse Ackermann function (Tamir, 1988) [17]. When the underlying network is a partial k-tree (k fixed), we exploit the geometry inherent in the problem and propose a two-level tree decomposition data structure which can be used to efficiently solve discrete p-center problems for small values of p

چکیده

در این مقاله نشان خواهیم داد که یک مسئله‌ی مکان‌ یابی p مرکز (تعداد مراکز بزرگ‌تر و برابر با 2 می ‌باشد) در شبکه‌های عمومی را می ‌توان به یک مسئله‌ ی معروف مقیاس کِلی تبدیل کرد ( آورماس و یاپ، 1991 میلادی) [15]. با این کار، می‌ توان به یک الگوریتم بهبود یافته‌ ی قابل‌ ملاحظه ‌ای برای موارد پیوسته از این مسئله و آن ‌هم با زمان اجرای O(m^pn^p/22^log∗ n logn) برای تعداد مراکز بزرگ ‌تر و برابر با 3 دست یافت؛ در این زمان اجرا، اندیس n بیانگر تعداد رئوس بوده، m نشان دهنده ی تعداد یال ها بوده و عبارت log^∗ n نیز لوگاریتم تکراری برای n را نشان می ‌دهد (کورمن و همکارانش 2001 میلادی) [10]. برای مقادیر p=2، زمان اجرای این الگوریتم بهبود یافته برابر با O(m²n log ²n) خواهد بود. بهترین نتیجه ‌ای که قبلاً برای این مسئله به دست آمده است، از پیچیدگی زمانی O(m^pn^pα(n) logn) برخوردار بوده که در آن، α(n) بیانگر معکوس نتیجه ‌ی تابع آکرمن می‌ باشد (آقای تامیر، 1988 میلادی) [17]. در زمانی که شبکه‌ ی تشکیل شده از این مکان‌ ها، یک شبکه ‌ای از k درخت جزئی (تعداد ثابتی از k) باشد، ما از هندسه ‌ی موجود از این شبکه در مسئله بهره ‌برداری کرده و یک ساختار داده ‌ای تجزیه ‌ی درختی 2 سطحی را پیشنهاد می‌ دهیم که می ‌تواند به منظور حل مسائل مکان ‌یابی p مرکز گسسته برای مقادیر کوچکی از p و آن ‌هم به شکلی کارآمد بکار گرفته شود. 

1-مقدمه

مسئله پی-مرکز را می ‌توان به عنوان یک شبکه ‌ی غیر جهت‌ دار وزن ‌دار به صورت G = (V (G), E(G)) (|V(G)| = n, |E(G)| = m = Ω(n)) تعریف کرد که در آن، هر رأس v ∈ V (G)دارای یک وزنِ غیر منفی w(v) بوده و هر یال e ∈ E(G) نیز دارای یک طول مثبت l(e) می‌ باشد. فرض کنید که A(G) بیانگر مجموعه ای پیوسته از نقاطی روی یال های G باشد. برای مقادیر x, y ∈ A(G)، عبارتِ π(x, y) نشان دهنده ی کوتاه ‌ترین مسیر در G از نقطه ی x به نقطه ی y می ‌باشد و d(x, y) نیز نشان دهنده ی طول مسیر π(x, y) می ‌باشد...