Weekly Activities

An efficient algorithm for generating all k-ary symmetric necklaces
Speaker: Pham Lan Anh (HUT)

Time: 9h30, Thursday 06 March 2014

Location: Room 301 (or 201), Building A5, Vietnam Institute of Mathematics, 18 Hoang Quoc Viet, Ha Noi

Abstract: A symmetric necklace is a necklace that this necklace and its reverse are in the same equivalence class under rotation. An efficient algorithm is the one that uses only a constant amount of computation per object, in an amortized sense. Such algorithms are also said to be constant amortized time (CAT) algorithms. In this paper, we first present some characteristics of symmetric necklaces, then propose an efficient algorithm for generating them and finally count the cardinality of this object class.

Back