کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331873 | 686963 | 2015 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Circulant graphs and GCD and LCM of subsets
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given two sets A and B of integers, we consider the problem of finding a set SâA of the smallest possible cardinality such the greatest common divisor of the elements of SâªB equals that of those of AâªB. The particular cases of B=â
and #B=1 are of special interest and have some links with graph theory. We also consider the corresponding question for the least common multiple of the elements. We establish NP-completeness and approximation results for these problems by relating them to the Set Cover Problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 134-138
Journal: Information Processing Letters - Volume 115, Issue 2, February 2015, Pages 134-138
نویسندگان
Joachim von zur Gathen, Igor E. Shparlinski,