| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331873 | Information Processing Letters | 2015 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Joachim von zur Gathen, Igor E. Shparlinski,