Projects per year
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 NPcompleteness and approximation results for these problems by relating them to the Set Cover Problem.
Original language  English 

Pages (fromto)  134138 
Number of pages  5 
Journal  Information Processing Letters 
Volume  115 
Issue number  2 
DOIs  
Publication status  Published  Feb 2015 
Externally published  Yes 
Keywords
 analysis of algorithms
 circulant graphs
 computational complexity
 graph algorithms
 minimum cover
Fingerprint Dive into the research topics of 'Circulant graphs and GCD and LCM of subsets'. Together they form a unique fingerprint.
Projects
 2 Finished

New Applications of Additive Combinatorics in Number Theory and Graph Theory
Mans, B., Shparlinski, I., MQRES, M. & PhD Contribution (ARC), P. C. (.
1/01/14 → 31/12/17
Project: Research

Lattices as a Constructive and Destructive Cryptographic Tool
Doche, C., Shparlinski, I., Steinfeld, R., Stehle, D., MQRES, M., PhD Contribution (ARC), P. C. (. & Newton, J.
31/07/11 → 31/12/14
Project: Research