کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10523913 957142 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal shift coloring of trees
ترجمه فارسی عنوان
بهینه تغییر رنگ درختان
کلمات کلیدی
رنگ آمیزی نمودار، تغییر رنگ، درختان، الگوریتم زمان چندجملهای،
ترجمه چکیده
این مقاله با مشکلی در برنامه ریزی باز کردن داروخانه ها در انتهای هفته و تعطیلات (تغییرات) مواجه شد. مشکل را می توان به عنوان یک مشکل رنگی در یک گراف مدل سازی کرد. در این مقاله ما بر روی مورد خاص تمرکز می کنیم که در آن گراف پایه یک درخت است یا، به طور کلی، آن را با یک متریک درخت تخصیص داده و ما یک الگوریتم زمان چندجملهای ارائه می دهیم. ما همچنین راه حل های بهینه برای درخت های ویژه مانند ستارگان و مسیرها را ارائه می دهیم.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش مقاله
بهینه تغییر رنگ درختان
چکیده انگلیسی
This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 42, Issue 4, June 2014, Pages 251-256
نویسندگان
, , ,