๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Shifts and loopless generation of k-ary trees

โœ Scribed by James F. Korsh; Seymour Lipschutz

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
388 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

A new shift operation on nodes of k-ary trees which preserves preorder node numbers is introduced. The shift graph SG,,k has as vertices all n-node k-ary trees and edges corresponding to one shift. The graph is proven to have a Hamiltonian path and an algorithm is presented which generates all n-node k-ary trees successively with constant time between them.

๐Ÿ“œ SIMILAR VOLUMES

A Loopless Gray-Code Algorithm for Listi
A Loopless Gray-Code Algorithm for Listing k-ary Trees
โœ Dominique Roelants van Baronaigien ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 91 KB

The bit sequence representation for k-ary trees is a sequence b , b , . . . , b of bits that is formed by doing a preorder traversal of the k-ary tree and writing a 1 when the visited subtree is not empty and a zero when the visited subtree is empty. The representation is well known and in the cas

Multiset Permutations and Loopless Gener
Multiset Permutations and Loopless Generation of Ordered Trees with Specified Degree Sequence
โœ James F. Korsh; Paul LaFollette ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 131 KB

An ordered tree with specified degree sequence and n internal nodes has a i ลฝ . nodes of degree i, where a s 1 q ร i y 1 a and n s ร a . This paper presents the first loopless algorithm for generating all ordered trees with specified degree sequence. It uses a new version of the algorithm for gener

Bandwidth of the complete k-ary tree
Bandwidth of the complete k-ary tree
โœ Lawren Smithline ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 524 KB

We determine, constructively, the bandwidth of the complete k-ary tree on d levels. By rectifying an algorithm of Chung (1988), we establish B( Tk,J = rk(kd -1)/(2d( k -1)) 1. ## 1. Praeludium The bandwidth problem for a graph G is a question about numbering the vertices of G so the maximum differ

Onk-ary spanning trees of tournaments
Onk-ary spanning trees of tournaments
โœ Lu, Xiaoyun; Wang, Da-Wei; Chang, Gerard J.; Lin, In-Jen; Wong, C. K. ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 114 KB

It is well known that every tournament contains a Hamiltonian path, which can be restated as that every tournament contains a unary spanning tree. The purpose of this article is to study the general problem of whether a tournament contains a k-ary spanning tree. In particular, we prove that, for any