A fast algorithm to generate unlabeled necklaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast algorithm to generate unlabeled necklaces

Full text

Pdf (583 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 256 - 262

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Frank Ruskey	Department of Computer Science, University of Victoria, Victoria, B.C., CANADA
Joe Sawada	Department of Computer Science, University of Victoria, Victoria, B.C., CANADA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 28, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	K. Cattell, F. Ruskey, J. Sawada, C.R. Miers, M. Serra, Efficient algorithms for generating unlabeled necklaces and irreducible polynomials over GF(2), manuscript in revision, 1998.
	2	J. Berstel , M. Pocchiola, Average cost of Duval's algorithm for generating Lyndon words, Theoretical Computer Science, v.132 n.1-2, p.415-425, Sept. 26, 1994 [doi>10.1016/0304-3975(94)00013-1 ]
	3	J-P. Dural, Factoring words over an ordered alphabet, Journal of Algorithms, 4 (1983), 363-381.
	4	J.-P. Duval, Generation of a section of conjugation classes and Lyndon word tree of limited length, Theoretical Computer Science, v.60 n.3, p.255-283, September 1988 [doi>10.1016/0304-3975(88)90113-2 ]
	5	M. C. Er, A fast algorithm for generating set partitions, The Computer Journal, v.31 n.3, p.283-284, June 1988 [doi>10.1093/comjnl/31.3.283]
	6	H Fredricksen , I J Kessler, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, v.61 n.2-3, p.181-188, Sept. 1986 [doi>10.1016/0012-365X(86)90089-0 ]
	7	H. Fredricksen and I.J. Maiorana, Necklaces of beads in k colors and k-ary de Bruijn sequences, Discrete Mathematics, 23 (1978) 207-210.
	8	E.N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Mathematics, 5 (1961) 657- 665.
	9	Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	10	R.A. Kaye, A Gray code for set partitions, information Processing Letters, 5 (1976) 171-173.
	11	M. Lothaire, Combinatorics on Words, Cambridge University Press, 1983.
	12	R.L. Miller, Necklaces, symmetries, and self-reciprocal polynomials, Discrete Math., 22 (1978) 25-33.
	13	Andrzej Proskurowski , Frank Ruskey , Malcolm Smith, Analysis of Algorithms for Listing Equivalence Classes of k-ary Strings, SIAM Journal on Discrete Mathematics, v.11 n.1, p.94-109, Feb. 1998 [doi>10.1137/S0895480192234009]
	14	Frank Ruskey , Carla Savage , Terry Min Yih Wang, Generating necklaces, Journal of Algorithms, v.13 n.3, p.414-430, Sept. 1992 [doi>10.1016/0196-6774(92)90047-G]
	15	Joe Sawada , Frank Ruskey, An efficient algorithm for generating necklaces with fixed density, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.752-758, January 17-19, 1999, Baltimore, Maryland, United States
	16	F. Ruskey and J. Sawada, Generating necklaces with a forbidden substring, manuscript, 1999.
	17	J. Sawada, Generating bracelets in constant amortized time, manuscript, 1999.