Loopless Generation of Trees with Specified Degrees

An ordered tree with specified degrees and $n$ nodes has $a_{i}$ nodes of degree $i$ where $a_{0} = 1+\sum _{i = 1,h}(i-1)a_{i}$ and $n = \sum_{i = 0,h}a_{i}$. This paper presents a new and simpler loopless algorithm for generating all ordered trees with specified degrees. When $a_{k} = N$, $a_{0} =...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 2002-01, Vol.45 (3), p.364-372
Main Authors: Korsh, James F, LaFollette, Paul
Format: Article
Language:English
Subjects:
Algorithms
Codes
Trees
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An ordered tree with specified degrees and $n$ nodes has $a_{i}$ nodes of degree $i$ where $a_{0} = 1+\sum _{i = 1,h}(i-1)a_{i}$ and $n = \sum_{i = 0,h}a_{i}$. This paper presents a new and simpler loopless algorithm for generating all ordered trees with specified degrees. When $a_{k} = N$, $a_{0} = (k-1)N+1$ and all other $a_{i}$'s are 0, then all $N$ node $k$-ary trees are generated.
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/45.3.364