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.


Selected papers that refer to this paper:
Back to list of publications.