Circulant graphs and GCD and LCM of subsets

Joachim Von Zur Gathen, Igor E. Shparlinski*

*Corresponding author for this work

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)134-138
Number of pages5
JournalInformation Processing Letters
Volume115
Issue number2
DOIs
Publication statusPublished - Feb 2015
Externally publishedYes

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.

Cite this