Frank Ruskey - Selected Publications

This page will always be under construction. My publication lists are slowly being converted to form shown below. You can download an abstract and DVI and POSTSCRIPT versions of the papers. This page is provided as a convenience only. The corresponding journal articles represent the official versions of these papers. In many cases the journal versions have different formatting and thus page numbers may differ. The abstract file contains (or will contain) the number of bytes of the dvi and postscript files and additional notes and links related to the papers. If the icon is red then the corresponding file is not yet available; don't waste your time clicking on it.

Please send me a note if you download one of these files. It is always nice to know who is reading your papers.

2020

2019

V. Irvine, S. Melczer and F. Ruskey, Vertically constrained Motzkin-like paths inspired by Bobbin lace, Electronic Journal of Combinatorics, to appear.

2018

2017

V. Irvine and F. Ruskey, Aspects of Symmetry in Bobbin Lace, Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture, pages 205-212. Tessellations Publishing, 2017.

P. Burcsi, G. Fici, Z. Lipták, F. Ruskey and J. Sawada, On prefix normal words and prefix normal forms, Theoretical Computer Science, 659: 1-13.

2016

F. Ruskey, Combinatorial Gray Code, Encyclopedia of Algorithms 2016: 342-347.

2015

G. Pruesse and F. Ruskey, All Simple Venn Diagrams are Hamiltonian, submitted.

P. Bursci, M. Celaya and F. Ruskey, An infinite nested recurrence relation that takes on Fibonacci values at Fibonacci indices, submitted manuscript.

2014

V. Irvine and F. Ruskey, Developing a Mathematical Model for Bobbin Lace, Journal of Mathematics and the Arts, 8 (2014) 95-110.

K. Mamakani and F. Ruskey, New Roses: Simple Symmetric Venn Diagrams with 11 and 13 Curves, Discrete and Computational Geometry, 52 (2014) 71-87.

P. Burcsi, G. Fici, Z. Lipták, F. Ruskey and J. Sawada, Normal, Abby Normal, Prefix Normal, FUN with Algorithms 2014, LNCS vol. 8496, pp. 74-88.

P. Burcsi, G. Fici, Z. Lipták, F. Ruskey and J. Sawada, On Combinatorial Generation of Prefix Normal Words, Combinatorial Pattern Matching, CPM 2014, LNCS vol. 8486, pp. 60-69.

M. Celaya and F. Ruskey, A Morphological Analysis of Vileness, GASCOM 2014, Bertinoro, Italy.

2013

A. Erickson and F. Ruskey, Domino Tatami Tiling is NP-Complete, IWOCA 2013, International Workshop on Combinatorial Algorithms, LNCS 8288, pp. 140-149, 2013.

M. Celaya and F. Ruskey, On morphisms and nested recurrence relations, 2013, to be submitted to a journal.

K. Mamakani and F. Ruskey, Simple Spherical Venn diagrams with Isometry Groups of Order Eight, 2012, submitted to a journal.

Q. Yang, J. Ellis, K. Mamakani and F. Ruskey, Parallel and sequential in-place permuting and shuffling using involutions, (arXiv:1204.1958v2), Information Processing Letters, 113 (2013) 386-391.

C.R. Miers and F. Ruskey Counting strings over over Z_2^d with given elementary symmetric function evaluations, Formal Power Series and Algebraic Combinatorics (FPSAC), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS proc. AS, 2013, 927-938.

2012

S. Chandran, A. Das, and and F. Ruskey, Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions , submitted manuscript.

A. Erickson and F. Ruskey, Enumerating tatmi mat arrangements of square grids with v vertical dimers, submitted manuscript.

B. Bultena, M. Klimesh, and F. Ruskey, Minimum Area Polyomino Venn Diagrams, Journal of Computational Geometry, (3)1 (2012) 154-167.

A. Holroyd, F. Ruskey and A. Williams, Shorthand Universal Cycles for Permutations, Algorithmica, 64 (2012) 215-245.

M. Celaya and F. Ruskey, AMM Problem 11651, American Mathematical Monthly, 119 (2012) 522.

A. Erickson, A. Isgur, B.W. Jackson, F. Ruskey and S. Tanny, Nested Recurrence Relations with Conolly-like Solutions, SIAM J. Discrete Mathematics, 26 2012, pp. 206-238 (33 pages).

M. Celaya and F. Ruskey, An Undecidable Nested Recurrence Relation (arXiv:1203.0586v1): CiE 2012, Cambridge, England, June 2012, LNCS 7318 107-117.

S. Durocher, B. Li, D. Mondal, F. Ruskey and A. Williams, Cool-lex order and k-ary Catalan structures, Journal of Discrete Algorithms, 16 (2012) 287-307.

F. Ruskey, J. Woodcock and Y. Yamauchi, Counting and Computing the Rand and Block Distances of Pairs of Set Partitions, Journal of Discrete Algorithms, 16 (2012) 236-248.

K. Mamakani, W. Myrvold and F. Ruskey, Generating Simple Convex Venn Diagrams, Journal of Discrete Algorithms, 16 (2012) 270-286.

F. Ruskey, J. Sawada, and A. Williams, Journal of Discrete Algorithms, 16 (2012) 270-286.

F. Ruskey, J. Sawada, and A. Williams, De Bruijn Sequences for Fixed-Weight Binary Strings, SIAM Journal on Discrete Mathematics, 26 (2012) 605-617.

F. Ruskey, J. Sawada, and A. Williams, Binary Bubble Languages, Journal of Combinatorial Theory, Ser. A 119(1) (2012) 155-169.

F. Ruskey and A. Williams, The Feline Josephus Problem, Theory of Computing Systems, 50 (2012) 20-34. DOI: 10.1007/s00224-011-9343-6.

2011

F. Ruskey and M. Weston, Spherical Venn Diagrams with Involutory Isometries, Electronic Journal of Combinatorics, 18 (2011) #P191, 14 pages.

F. Ruskey, Teaching the Art of Computer Programming (TAOCP), Western Canadian Conference on Computing Education (WCCCE 2011), Prince George, B.C., May 6-7, 2011.

F. Ruskey and J. Woodcock, The Rand and block distance of pairs of set partitions, International Workshop on Combinatorial Algorithms, Victoria, 2011. LNCS 7056, 287-299.

K. Mamakani, W. Myrvold and F. Ruskey, Generating all Simple Convexly-drawable Polar Symmetric 6-Venn Diagrams, International Workshop on Combinatorial Algorithms, Victoria, 2011. LNCS, 7056, 275-286.

F. Ruskey, Fibonacci Meets Hofstadter, The Fibonacci Quarterly, 49 (2011), no. 3, 227-230.

M. Alekseyev and F. Ruskey, AMM Problem 11544, American Mathematical Monthly, 118 (2011) 84.

A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Structure and Enumeration of Monomer/Dimer Tatami Tilings, Electronic Journal of Combinatorics, 18(1) (2011) P109, 24 pages.

2010

F. Ruskey and Aaron Williams, An explicit universal cycle for the (n-1)-permutations of an n-set, ACM Transactions on Algorithms, Volume 6, Issue 3, Article 45 (June 2010), 12 pages.

A. Holroyd, F. Ruskey and A. Williams, Faster Generation of Shorthand Universal Cycles for Permutations, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 298-307.

A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.

T. Cao, K. Mamakani and F. Ruskey, Symmetric Monotone Venn Diagrams with Seven Curves, Fifth International Conference on Fun with Algorithms, June 2-4, Ischia Island, Italy. LNCS 6099, 331-342.

F. Ruskey and A. Williams, The Feline Josephus Problem, Fifth International Conference on Fun with Algorithms, June 2-4, Ischia Island, Italy. LNCS 6099, 343-354.

2009

F. Ruskey and J. Woodcock, Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics, Paper R126 (2009) 20 pages.

Franklin T. Adams-Watters and F. Ruskey, Generating functions for the digital sum and other digit counting sequences, Journal of Integer Sequences, Volume 12, Article 09.5.5, 9 pages, 2009.

F. Ruskey and C. Deugau, The combinatorics of certain k-ary meta-Fibonacci sequences, Journal of Integer Sequences, Volume 12, Article 09.4.3, 36 pages, 2009.

2008

F. Ruskey and Aaron Williams, Generating Balanced Parentheses and Binary Trees by Prefix Shifts, In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds., ACS. 107--115.

F. Ruskey, B. Stevens, and Mark Weston, Symmetric Venn Diagrams on the Sphere, in progress.

2007

F. Ruskey and Aaron Williams, The Coolest Way to Generate Combinations, Discrete Mathematics, 309 (2009) 5305-5320.

J. Carroll, F. Ruskey, and M. Weston, Which n-Venn diagrams can be drawn with convex k-gons?, Discrete and Computational Geometry, 37 (2007) 619-628.

Gilbert Lee, F. Ruskey, and Aaron Williams Hamming distance from irreducible polynomials over GF(2), International Conference on Analysis of Algorithms, Juan-les-pins, France, June 17-22, 2007. DMTCS proc. AH, 2007, 169-180.

S. Chow and F. Ruskey, Drawing Minimum Area Venn Diagrams using Polyominoes, Mathematics Magazine, Volume 80, No. 2, April 2007, pp. 91-103.

2006

F. Ruskey, Carla D. Savage, and Stan Wagon, The Search for Simple Symmetric Venn Diagrams, Notices of the American Mathematical Society, December 2006, pages 1304-1311.

S. Chow and F. Ruskey, Gray Codes for Polyominoes and a New Class of Distributive Lattices, Discrete Mathematics, 309 (2009) 5284-5297.

C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, Fourth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, September 18-22, 2006, Institut Élie Cartan, Nancy, France, 2006. DMTCS Proceedings Series, Volume AG, 203-214.

B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees, and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), #R26, 13 pages.

2005

M. Miller, J. Gimbert, F. Ruskey, and J. Ryan, Iterations of eccentric digraphs, Bulletin of the Institute of Combinatorics and its Applications, 45 (2005) 41-50.

S. Chow and F. Ruskey, Area-Proportional Drawings of Intersecting Families of Simple Closed Curves, 17th Canadian Conference on Computational Geometry, Proceedings, Pages 118-121.

N. Kube and F. Ruskey, Sequences that Satisfy a(n-a(n)) = 0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5, 8 pages.

F. Ruskey and Aaron Williams, Generating combinations by prefix shifts, COCOON 2005, The Eleventh International Computing and Combinatorics Conference, Kunming, China, 2005. Lecture Notes in Computer Science, 3595 (2005) 570-576.

S. Chow and F. Ruskey, Towards a General Solution to Drawing Area-Proportional Euler Diagrams, Electronic Notes in Theoretical Computer Science, Volume 134, Pages 3-18 (1 June 2005), Proceedings of the First International Workshop on Euler Diagrams (Euler 2004) 22-23 September 2004, Edited by P. Rodgers.

2004

C. Killian, F. Ruskey, C. Savage, and M. Weston, Half-Simple Symmetric Venn Diagrams, Electronic Journal of Combinatorics, 11 (2004) #R86, 22 pages.

F. Ruskey and M. Weston, More fun with symmetric Venn diagrams, Theory of Computing Systems, 39 (2006) 413-423. (Preliminary version appears in FUN 2004, Third International Conference on FUN with Algorithms, 235-246.)

C.R. Miers and F. Ruskey Counting Strings with Given Elementary Symmetric Function Evaluations II: Circular Strings, SIAM J. Discrete Mathematics, 18 (2004) 71-82.

C.R. Miers and F. Ruskey Counting Strings with Given Elementary Symmetric Function Evaluations I: Strings over Z_p with p Prime, SIAM J. Discrete Mathematics, 17 (2004) 675-685.

2003

S. Chow and F. Ruskey, Drawing Area Proportional Venn and Euler Diagrams, 11th International Symposium on Graph Drawing, Perugia, Italy, Lecture Notes in Computer Science, 2912 (2003) 466-477.

L.S. Chandran, L. Ibarra, F. Ruskey, and J. Sawada, Generating and characterizing the perfect elimination orderings of a chordal graph, Theoretical Computer Science, 307 (2003) 303-317.

F. Ruskey and J. Sawada, Generating Lyndon Brackets: a Basis for the n-th Homogeneous Component of the Free Lie Algebra, Journal of Algorithms, 46 (2003) 21-26.

F. Ruskey, and J. Sawada, Bent Hamilton Cycles in Grid Graphs, Electronic Journal of Combinatorics, #R1, 10 (2003) 18 pages.

S. Effler and F. Ruskey A CAT Algorithm for listing permutations with a given number of inversions, Information Processing Letters, 86/2 (2003) 107-112.

K. Cattell, F. Ruskey, C.R. Miers, J. Sawada, and M. Serra, The Number of Irreducible Polynomials Over GF(2) with Given Trace and Subtrace, Journal of Combinatorial Mathematics and Combinatorial Computing, 47 (November 2003) 31-64.

2002

J. Ellis, F. Ruskey, J. Sawada, and J. Simpson, Euclidean Strings, Theoretical Computer Science, 301 (2003) 321-340.

D.E. Knuth and F. Ruskey, Efficient Coroutine Generation of Constrained Gray Sequences (aka Deconstructing Coroutines), From Object-Orientation to Formal Methods: Dedicated to The Memory of Ole-Johan Dahl, LNCS 2635, Springer-Verlag, 2003.

2001

W. Myrvold and F. Ruskey, Ranking and Unranking Permutations in Linear Time, Information Processing Letters, 79 (2001) 281-284.

F. Ruskey, C.R. Miers, and J. Sawada, The Number of Lyndon Words and Irreducible Polynomials of Given Trace, SIAM J. Discrete Mathematics, 14 (2001) 240-245.

2000

T. Ball, D. Hoffman, F. Ruskey, R. Webber, and L. White, State Generation and Automated Class Testing, Software Testing, Verification and Reliability, Volume 10, Issue 3, September 2000, pages 149-170.

K. Cattell, F. Ruskey, J. Sawada, C.R. Miers, and M. Serra, Fast Algorithms to Generate Necklaces, Unlabelled Necklaces and Irreducible Polynomials over GF(2), J. Algorithms, 37 (2000) 267-282.

F. Ruskey and J. Sawada, Generating Necklaces and Strings with Forbidden Substrings, 6th Annual International Combinatorics and Computing Conference (COCOON), Sydney, Australia, July 2000. LNCS #1858 (2000) 330-339.

1999

B. Bultena, B. Grünbaum, and F. Ruskey, Convex Drawings of Intersecting Families of Simple Closed Curves, 1998. Presented at the 11th Canadian Conference on Computational Geometry, (1999), 18-21.

G. Li and F. Ruskey, The Advantages of Forward Thinking in Generating Rooted and Free Trees, 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1999) S939-940. (short form abstract).

J. Sawada and F. Ruskey, An Efficient Algorithm for Generating Necklaces with Fixed Density, presented at SODA (Symposium on Discrete Algorithms) 1999, (long form abstract).

J. Sawada and F. Ruskey, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.

D. Roelants van Baronaigien, F. Ruskey, and W.R. Engels, Faster Methods for Computing Randomization Tests in the Presence of Repeated Data Values, submitted to Computational Statistics, 1998.

1998

B. Bultena and F. Ruskey, Venn Diagrams with Few Vertices, Electronic Journal of Combinatorics, Volume 5, paper R44, 21 pages, 1998.

A. Bultena and F. Ruskey, An Eades-McKay Algorithm for Well-Formed Parentheses Strings, Information Processing Letters, 68 (1998) 255-259.

Colin Ramsay, Ian T. Roberts, and Frank Ruskey, Completely Separating Systems of k-Sets, Discrete Mathematics, 183 (1998) 265-275.

A. Proskurowski, F. Ruskey, and M. Smith, Analysis of Algorithms for Listing Equivalence Classes of k-ary Strings Induced by Simple Group Actions, SIAM Journal on Discrete Mathematics, 11 (1998) 94-109.

S. Chow and F. Ruskey, Searching for Symmetric Venn Diagrams, two-page abstract only. Workshop on Computational Graph Theory and Combinatorics, Victoria, 1999, pp. 37-38.

1997

R. F. Cohen, P. Eades, T. Lin and F. Ruskey, Three Dimensional Graph Drawing, Algorithmica, 17 (1997) 199-208.

1996

F. Ruskey and Carla Savage, A Gray Code for the Combinations of a Multiset, European Journal of Combinatorics, 17 (1996) 493-500.

A. Bultena and F. Ruskey, Transition Restricted Gray Codes, Electronic Journal of Combinatorics, 3 (1996), paper R11.

1995

G. Pruesse and F. Ruskey, The Prism of the Acyclic Orientation Graph is Hamiltonian, Electronic Journal of Combinatorics, 2 (1995), paper R5..

F. Ruskey, M. Jiang and A. Weston, On the Hamiltonicity of Directed sigma-tau Cayley Graphs (Or: A Tale of Backtracking), Discrete Applied Mathematics, 57 (1995) 75-83.

1994

Gara Pruesse and Frank Ruskey, Generating Linear Extensions Fast, SIAM Journal on Computing, Vol. 23, No. 2, pp. 373-386, April 1994.

Frank Ruskey, Peter Eades, Bob Cohen, and Aaron Scott, Alley CATs in Search of Good Homes, Congressus Numerantium, 102 (1994) 97-110.

1993

F. Ruskey and Carla Savage, Hamilton Cycles which Extend Transposition Matchings in Cayley Graphs of S_n, SIAM Journal on Discrete Mathematics, 6 (1993) 152-166.

F. Ruskey, Simple combinatorial Gray codes constructed by reversing sublists, 4th ISAAC (International Symposium on Algorithms and Computation), Lecture Notes in Computer Science, #762 (1993) 201-208.

G. Pruesse and F. Ruskey, Gray Codes from Antimatroids, Order, 10 (1993) 239-252.

Y. Koda and F. Ruskey, A Gray Code for the Ideals of a Forest Poset, Journal of Algorithms, 15 (1993) 324-340.

Joan Lucas, Dominique Roelants van Baronaigien, and Frank Ruskey, On Rotations and the Generation of Binary Trees, Journal of Algorithms, 15 (1993) 343-366.

Dominique Roelants van Baronaigien and Frank Ruskey, Generating Subsets with a Given Sum, Journal of Combinatorial Mathematics and Combinatorial Computing, 14 (1993) 87-96.

1992

Frank Ruskey, Generating Linear Extensions of Posets by Transpositions, Journal of Combinatorial Theory (B), 54 (1992) 77-101.

C.W. Ko and F. Ruskey, Generating Permutations of a Bag by Interchanges, Information Processing Letters, 41 (1992) 263-269.

F. Ruskey, C. Savage, and T. Wang, Generating Necklaces, J. Algorithms, 13 (1992) 414-430.

1991

G. Pruesse and F.Ruskey, Generating the Linear Extensions of Certain Posets by Transpositions, SIAM J. Discrete Mathematics 4 (1991) 413-422.

1990

Bruce Bauslaugh and Frank Ruskey, Generating Alternating Permutations Lexicographically, BIT, 30 (1990) 17-26.

Frank Ruskey and Andrzej Proskurowski, Generating Binary Trees by Transpositions, Journal of Algorithms, 11 (1990) 68-84.

1989

F.Ruskey, Transposition Generation of Alternating Permutations, Order 6 (1989) 227-233.

1988

Frank Ruskey, Adjacent Interchange Generation of Combinations, Journal of Algorithms, 9 (1988) 162-180.

Tim Hough and Frank Ruskey, An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm, Journal of Combinatorial Mathematics and Combinatorial Computing, 4 (1988) 79-86.