کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418715 681712 2016 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A constant time algorithm for some optimization problems in rotagraphs and fasciagraphs
ترجمه فارسی عنوان
الگوریتم زمان ثابت برای برخی از مسائل بهینه سازی در روتاگراف‌ها و فاشیوگراف ها
کلمات کلیدی
مسائل ترکیبی بهینه سازی؛ الگوریتم زمان ثابت؛ شبکه ها؛ 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
نویسندگان
, , ,