Title
An Efficient Scheme for the Generation of Ordered Trees in Constant Amortized Time
Date Issued
04 January 2021
Access level
open access
Resource Type
conference paper
Author(s)
Waseda University
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Trees are useful entities allowing to model data structures and hierarchical relationships in networked decision systems ubiquitously. An ordered tree is a rooted tree where the order of the subtrees (children) of a node is significant. In combinatorial optimization, generating ordered trees is relevant to evaluate candidate combinatorial objects. In this paper, we present an algebraic scheme to generate ordered trees with $n$ vertices with utmost efficiency; whereby our approach uses $O$ (n) space and $O$ (1) time in average per tree. Our computational studies have shown the feasibility and efficiency to generate ordered trees in constant time in average, in about one tenth of a millisecond per ordered tree. Due to the 1-1 bijective nature to other combinatorial classes, our approach is favorable to study the generation of binary trees with $n$ external nodes, trees with $n$ nodes, legal sequences of $n$ pairs of parentheses, triangulated n-gons, gambler's sequences and lattice paths. We believe our scheme may find its use in devising algorithms for planning and combinatorial optimization involving Catalan numbers.
Language
English
OCDE Knowledge area
Estadísticas, Probabilidad Matemáticas aplicadas
Scopus EID
2-s2.0-85103740237
ISBN of the container
9780738105086
Conference
Proceedings of the 2021 15th International Conference on Ubiquitous Information Management and Communication, IMCOM 2021
Sponsor(s)
ACKNOWLEDGMENT This research was supported by JSPS KAKENHI Grant Number 20K11998.
Sources of information: Directorio de Producción Científica Scopus