کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875720 1441982 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal algorithms for inverse vertex obnoxious center location problems on graphs
ترجمه فارسی عنوان
الگوریتم های بهینه برای حل مسائل مربوط به موقعیت مکانی مرکب در نمودار های معکوس
کلمات کلیدی
موقعیت مرکزی ناخوشایند، بهینه سازی ترکیبی، بهینه سازی معکوس، پیچیدگی زمان،
ترجمه چکیده
در یک حلقه معکوس، مسئله محل سکونت مرکزی ناخوشایند، هدف این است که طول لبه ها را با حداقل هزینه کلی با توجه به مرزهای اصلاح، تغییر دهیم به طوری که یک حلقه از پیش تعیین شده تبدیل به یک مرکز مرکزی ناگهانی در زیر طول لبه جدید می شود. ما یک روش ترکیب ترکیبی خطی برای مشکل با افزایش طول لبه داریم. برای پرونده کاهش، یک الگوریتم با زمان اجرا مکعبی طراحی شده است. ما همچنین نشان می دهیم که مشکل با افزایش و کاهش طول لبه می تواند در زمان سکسی حل شود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم های بهینه برای حل مسائل مربوط به موقعیت مکانی مرکب در نمودار های معکوس
چکیده انگلیسی
In an inverse vertex obnoxious center location problem, the aim is to modify the edge lengths at minimum total cost with respect to the modification bounds such that a predetermined vertex becomes a vertex obnoxious center location under the new edge lengths. We develop a linear time combinatorial method for the problem with edge length augmentation. For the reduction case, an algorithm with cubic running time is devised. We also show that the problem with both edge length augmentation and reduction can be solved in sextic time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 707, 10 January 2018, Pages 36-45
نویسندگان
, ,