Algorithmic Solution of Two Combinatorial Problems
Frank Ruskey,
Department of Computer Science,
University of Victoria.
Abstract:
LATER
The main purpose of this page is to provide a convenient place
for some scans of pages from my Ph.D. thesis. It was written using
a IBM selectric typewriter (the ones where different "balls"
were used to get different fonts and symbols) and lots of
white-out.
Most of the thesis ended up in publication in one form or
the other in one of the following papers:
-
F. Ruskey and T.C. Hu,
Generating Binary Trees Lexicographically,
SIAM J. Computing, 6 (1977) 745-758, (MR 57 #18212).
[Pre-thesis, using level numbers of the leaves.]
-
F. Ruskey,
Generating t-ary Trees Lexicographically,
SIAM J. Computing, 7 (1978) 424-439, (MR 80f:68033).
[Pre-thesis, using level numbers of the leaves.]
-
T.C. Hu and F. Ruskey,
Circular Cuts in a Network,
Mathematics of O.R., 5 (1980) 422-434, (MR 81j:90121).
-
F. Ruskey,
Listing and Counting Subtrees of a Tree,
SIAM J. Computing, 10 (1981) 141-150, (MR 82j:68066).
[Only part of this is in the thesis.]
Here are the page scans from the sections on ranking
and unranking binary trees:
Committee: T.C. Hu (supervisor), James R. Bunch,
Michael L. Fredman, Walter J. Savitch, and
Stanley G. Williamson.
The corrected page 24 changes the while loop condition from
m > 0 to m > 0 and adds two pairs of missing
square brackets for the array references to
left and right.
My thanks to Antti
Karttunen for noting these typos.
Back
to Frank Ruskey's publication list.
