Testing set proportionality and the Ádám isomorphism of circulant graphs

Don Coppersmith; Nick Howgrave-Graham; Phong Q. Nguyễn; Igor E. Shparlinski

doi:10.1016/j.jda.2005.06.003

Testing set proportionality and the Ádám isomorphism of circulant graphs

Don Coppersmith, Nick Howgrave-Graham, Phong Q. Nguyễn, Igor E. Shparlinski^*

^*Corresponding author for this work

School of Computing

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

1 Citation (Scopus)

Abstract

Given two k element subsets S, T ⊆ Z_n, we give a quasi-linear algorithm to either find λ ∈ Z_n ^* such that S = λ T or prove that no such λ exists. This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.

Original language	English
Pages (from-to)	324-335
Number of pages	12
Journal	Journal of Discrete Algorithms
Volume	4
Issue number	2
DOIs	https://doi.org/10.1016/j.jda.2005.06.003
Publication status	Published - Jun 2006

Access to Document

10.1016/j.jda.2005.06.003

Cite this

@article{2cd573bd0c9f4a358b1bc2c269dd3b7b,

title = "Testing set proportionality and the {\'A}d{\'a}m isomorphism of circulant graphs",

abstract = "Given two k element subsets S, T ⊆ Zn, we give a quasi-linear algorithm to either find λ ∈ Zn * such that S = λ T or prove that no such λ exists. This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.",

author = "Don Coppersmith and Nick Howgrave-Graham and Nguyễn, {Phong Q.} and Shparlinski, {Igor E.}",

year = "2006",

month = jun,

doi = "10.1016/j.jda.2005.06.003",

language = "English",

volume = "4",

pages = "324--335",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Testing set proportionality and the Ádám isomorphism of circulant graphs

AU - Coppersmith, Don

AU - Howgrave-Graham, Nick

AU - Nguyễn, Phong Q.

AU - Shparlinski, Igor E.

PY - 2006/6

Y1 - 2006/6

N2 - Given two k element subsets S, T ⊆ Zn, we give a quasi-linear algorithm to either find λ ∈ Zn * such that S = λ T or prove that no such λ exists. This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.

AB - Given two k element subsets S, T ⊆ Zn, we give a quasi-linear algorithm to either find λ ∈ Zn * such that S = λ T or prove that no such λ exists. This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.

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

U2 - 10.1016/j.jda.2005.06.003

DO - 10.1016/j.jda.2005.06.003

M3 - Article

AN - SCOPUS:33646271596

SN - 1570-8667

VL - 4

SP - 324

EP - 335

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 2

ER -

Testing set proportionality and the Ádám isomorphism of circulant graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this