Testing set proportionality and the Ádá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. © 2005 Elsevier B.V. All rights reserved.