Abstract
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(mpnp/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(m2n log 2n). The previous best result for the problem is O(mpnpα(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(mpnp/22log∗ n logn) برای تعداد مراکز بزرگ تر و برابر با 3 دست یافت؛ در این زمان اجرا، اندیس n بیانگر تعداد رئوس بوده، m نشان دهنده ی تعداد یال ها بوده و عبارت log∗ n نیز لوگاریتم تکراری برای n را نشان می دهد (کورمن و همکارانش 2001 میلادی) [10]. برای مقادیر p=2، زمان اجرای این الگوریتم بهبود یافته برابر با O(m2n log 2n) خواهد بود. بهترین نتیجه ای که قبلاً برای این مسئله به دست آمده است، از پیچیدگی زمانی O(mpnpα(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) می باشد...