چکیده
در این مقاله نشان خواهیم داد که یک مسئله‌ی مکان یابی 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) می باشد...