Constant Time Generation of Free Trees
Copyright policy )Constant Time Generation of Free Trees
The technique of \textit{T. Beyer} and \textit{S. M. Hedetniemi} [SIAM J. Comput. 9, 706-712 (1980; Zbl 0453.05020)] for generating all rooted trees of size n by applying a successor function on canonical level sequences is extended to generate all free (unrooted) trees. A primary sequence is defined among all the canonical level sequences belonging to isomorphic trees by rooting at a lexicographically first central node. The successor function is adapted to these sequences. The algorithm uses O(n) space and O(n) average time. Its pseudocode is given.
- Australian National University Australia
- University of Waterloo Canada
algorithm, Graph theory (including graph drawing) in computer science, unrooted tree, successor function, enumeration of trees, tree generation, Trees
algorithm, Graph theory (including graph drawing) in computer science, unrooted tree, successor function, enumeration of trees, tree generation, Trees
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).50 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!