Abstract: Alley CATs in Search of Good Homes

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 non-decreasing sequence of the out-degrees 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 non-increasing 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) 97-110.
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, Erdos-Gallai test in linear time, Combinatorica, ????.
Antal Iványi, Reconstruction of complete interval tournaments, II. Acta Univ. Sapientiae, Informatica, 2 (2010) 47-71.
Matthias Dehmer, Strukturelle Analyse Web-basierter Dokumente, (Book), Deutscher Universitats-Verlag/GWV Fachverlage GmbH, Wiesbaden 2006.
R. Hemashinha, An algorithm to generate tournament score sequences, Mathematical and Computer Modelling, 37 (2003) 377-383.
J. M. Nolan, V. Sivaraman, C. D. Savage and P. K. Tiwari, "Graphical Basis Partitions", Graphs and Combinatorics, 14(3):241-261, 1998.

Back to list of publications.