Circulant graphs and GCD and LCM of subsets

Joachim Von Zur Gathen; Igor E. Shparlinski

doi:10.1016/j.ipl.2014.07.014

Circulant graphs and GCD and LCM of subsets

Joachim Von Zur Gathen, Igor E. Shparlinski^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	134-138
Number of pages	5
Journal	Information Processing Letters
Volume	115
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2014.07.014
Publication status	Published - Feb 2015
Externally published	Yes

Keywords

analysis of algorithms
circulant graphs
computational complexity
graph algorithms
minimum cover

Access to Document

10.1016/j.ipl.2014.07.014

Cite this

@article{7ce3f8d6882a4e7e8ff51228bea23da9,

title = "Circulant graphs and GCD and LCM of subsets",

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.",

keywords = "analysis of algorithms, circulant graphs, computational complexity, graph algorithms, minimum cover",

author = "{Von Zur Gathen}, Joachim and Shparlinski, {Igor E.}",

year = "2015",

month = feb,

doi = "10.1016/j.ipl.2014.07.014",

language = "English",

volume = "115",

pages = "134--138",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Circulant graphs and GCD and LCM of subsets

AU - Von Zur Gathen, Joachim

AU - Shparlinski, Igor E.

PY - 2015/2

Y1 - 2015/2

N2 - 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.

AB - 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.

KW - analysis of algorithms

KW - circulant graphs

KW - computational complexity

KW - graph algorithms

KW - minimum cover

UR - http://www.scopus.com/inward/record.url?scp=85028111012&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP110100628

UR - http://purl.org/au-research/grants/arc/DP140100118

U2 - 10.1016/j.ipl.2014.07.014

DO - 10.1016/j.ipl.2014.07.014

M3 - Article

AN - SCOPUS:85028111012

SN - 0020-0190

VL - 115

SP - 134

EP - 138

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Circulant graphs and GCD and LCM of subsets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

New Applications of Additive Combinatorics in Number Theory and Graph Theory

Lattices as a Constructive and Destructive Cryptographic Tool

Cite this

Circulant graphs and GCD and LCM of subsets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

New Applications of Additive Combinatorics in Number Theory and Graph Theory

Lattices as a Constructive and Destructive Cryptographic Tool

Cite this