Alley CATs in Search of Good Homes
Frank Ruskey, Department of Computer Science,
University of Victoria, Canada.
Peter Eades, Department of Computer Science,
University of Newcastle, Australia.
Bob Cohen, Department of Computer Science,
University of Newcastle, Australia.
Aaron Scott, Department of Computer Science,
University of Newcastle, Australia.
Abstract:
A score sequence of a tournament is a monotonically
nondecreasing sequence of the outdegrees of its
vertices. We develop two algorithms that generate all
score sequences, each of which appears to use only a constant
amount of computation per sequence produced.
A degree sequence of a graph is a monotonically
nonincreasing sequence of the degrees of its vertices.
We develop an algorithm that generates all
degree sequences of given length and observe that
the algorithm does only constant computation per
sequence produced. This algorithm is extended to
generate degree sequences of connected graphs, and
of biconnected graphs.
 The postscript file is 211,809 bytes,
the dvi file is 46,084 bytes.
 Presented at 25th S.E. Conference on Combinatorics, Graph Theory, and Computing,
Congressus Numerantium, 102 (1994) 97110.
 An implementation is available; write to
Frank Ruskey.
 The algorithms are used in the
"Object Server."
From there select "Numerical Partitions and Relatives" and then "Degree Sequences."
Selected papers that refer to this paper:

Antal Iványi and Loránd Lucz,
ErdosGallai test in linear time,
Combinatorica, ????.

Antal Iványi,
Reconstruction of complete interval tournaments, II.
Acta Univ. Sapientiae, Informatica, 2 (2010) 4771.

Matthias Dehmer,
Strukturelle Analyse Webbasierter Dokumente,
(Book), Deutscher UniversitatsVerlag/GWV Fachverlage GmbH, Wiesbaden 2006.

R. Hemashinha,
An algorithm to generate tournament score sequences,
Mathematical and Computer Modelling, 37 (2003) 377383.

J. M. Nolan, V. Sivaraman, C. D. Savage and P. K. Tiwari, "Graphical Basis Partitions",
Graphs and Combinatorics, 14(3):241261, 1998.
Back to list of publications.