کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418715 | 681712 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
ترجمه فارسی عنوان
الگوریتم زمان ثابت برای برخی از مسائل بهینه سازی در روتاگرافها و فاشیوگراف ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسائل ترکیبی بهینه سازی؛ الگوریتم زمان ثابت؛ شبکه ها؛ Fasciagraphs؛ روتوگرافها؛ جبر Min-Plus
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 208, 31 July 2016, Pages 27–40
Journal: Discrete Applied Mathematics - Volume 208, 31 July 2016, Pages 27–40
نویسندگان
M. Bouznif, J. Moncel, M. Preissmann,