علوم رایانشی

علوم رایانشی

معکوس مسئله مکان‌یابی 1-مرکز روی گراف دور با افزایش طول یال‌ها

نوع مقاله : مقاله پژوهشی

نویسندگان
گروه ریاضی کاربردی و علوم کامپیوتر، دانشکده علوم ریاضی، دانشگاه صنعتی شاهرود، شاهرود، ایران
10.22034/csj.2025.237375
چکیده
در سال‌های اخیر معکوس مسائل مکان‌یابی روی شبکه‌ها موضوع تعداد زیادی از تحقیقات بوده است. مسئله مکان‌یابی 1-مرکز مطلق در یک شبکه عبارت است از یافتن یک نقطه روی شبکه به عنوان سرویس‌دهنده به طوری که فاصله دورترین نقطه روی گراف تا سرویس‌دهنده حداقل شود. در این مقاله به بررسی معکوس مسئله مکان‌یابی 1-مرکز مطلق روی یک گراف دور بدون وزن می‌پردازیم. یک گراف دور یک مسیر بسته است به طوری که درجه هر راس گراف 2 است. در معکوس مسئله مکان‌یابی 1-مرکز مطلق روی یک گراف دور یک راس در گراف مشخص شده است و هدف این است تا طول یال‌های گراف دور را افزایش دهیم به طوری که با انجام کمترین هزینه راس مشخص شده با طول یال‌های جدید یک 1-مرکز مطلق گراف دور باشد. در این مقاله یک الگوریتم ترکیبیاتی برای حل این مسئله پیشنهاد می‌کنیم به طوری که پیچیدگی زمانی الگوریتم  برای گراف‌های دور با  راس خواهد بود.
کلیدواژه‌ها
موضوعات

[1] Daskin, M. (1997). Network and discrete location: Modeles, algorithms and applications. Wiley, New York.
[2] Drezner, Z., Hamacher, H. W. (Eds.). (2001). Facility location: applications and theory. Springer Science and Business Media.
[3] Nazari, M., Fathali, J., Nazari, M., Varedi Koulaei, S.M. (2018). Inverse of Backup 2-Median Problems with Variable Edge Lengths and Vertex Weight on Trees and Variable Coordinates on the Plane. Production and Operations Management. 9(2), 115-137.
[4] Galavii, M. (2010). The inverse 1-median problem on a tree and on a path, Electron. Notes Discrete Math. 36, 1241-1248.
[5] Guan, X., & Zhang, B. (2011). Inverse 1-median problem on trees under weighted Hamming distance, J. Glob. Opt. 54, 75-82.
[6] Pham, V.H., & Nguyen, K.T. (2019). Inverse 1-median problem on trees under mixed rectilinear and Chebyshev norms, Theoret. Comput. Sci. 795, 119-127.
[7] Burkard, R.E., Pleschiutschnig, C., & Zhang, J.Z. (2008). The inverse 1-median problem on a cycle, Discrete Optim. 5, 242-253.
[8] Nguyen, K.T. (2016). Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory Appl. 168, 944-957.
[9] Nazari, M., & Fathali, J. (2023). Inverse and reverse 2-facility location problems with equality measures on a network. Iranian Journal of Mathematical Sciences and Informatics. 18(1), 211-225.
[11] Cai, M.C., Yang, X.G., & Zhang, J.Z. (1999). The complexity analysis of the inverse center location problem, J. Glob. Optim. 15, 213-218.
[12] Alizadeh, B., Burkard, R.E., & Pferschy, U. (2009). Inverse 1-center location problems with edge length augmentation on trees, Computing. 86, 331-343.
[13] Alizadeh, B., & Burkard, R.E. (2011). Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks. 58, 190-200.
[14] Hasanzadeh, M., Alizadeh, B., & Baroughi, F. (2024). Optimal algorithms for inverse obnoxious center location problems under the weighted Chebyshev and Hamming cost norms on networks, Optimization 73(3), 545-574.
[15] Nguyen, K. T. (2019). The inverse 1-center problem on cycles with variable edge lengths, Central European Journal of Operations Research. 27, 263-274.