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's always nice to know who is reading your papers.

2009

B. Bultena, M. Klimesh, and F. Ruskey, Minimum Area Venn Diagrams, in preparation.

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

F. Ruskey and A. Williams, Fixed-Weight de Bruijn Cycles, submitted to some famous conference.

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.

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

2008

F. Ruskey and Aaron Williams, An explicit universal cycle for the (n-1)-permutations of an n-set, ACM Transactions on Algorithms, to appear.

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, in press.

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 III: Strings over Z_2^d, manuscript in progress, 2004.

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, Fast Generation of all 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

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.

1987

T.C. Hu, Y.S. Kuo, and F. Ruskey, Some Optimum Algorithms for Scheduling Problems with Changeover Costs, Journal of The Operations Research Society of America (JORSA), 35 (1987) 94-99.

1981

Frank Ruskey, Listing and Counting Subtrees of a Tree, SIAM Journal on Computing, 10 (1981) 141-150.

1978

Frank Ruskey Algorithmic Solution of Two Combinatorial Problems Department of Applied Physics and Information Science, 1978.

Thanks for Thanks

The Book