2021年
An Efficient Scheme for the Generation of Ordered Trees in Constant Amortized Time.
15th International Conference on Ubiquitous Information Management and Communication(IMCOM)
- ,
- 巻
- abs/2011.03636
- 号
- 開始ページ
- 1
- 終了ページ
- 8
- 記述言語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1109/IMCOM51814.2021.9377349
- 出版者・発行元
- IEEE
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.
- リンク情報
-
- DOI
- https://doi.org/10.1109/IMCOM51814.2021.9377349
- DBLP
- https://dblp.uni-trier.de/rec/conf/icuimc/ParqueM21
- URL
- https://dblp.uni-trier.de/rec/conf/icuimc/2021
- URL
- https://dblp.uni-trier.de/db/conf/icuimc/imcom2021.html#ParqueM21
- Scopus
- https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85103740237&origin=inward
- Scopus Citedby
- https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85103740237&origin=inward
- ID情報
-
- DOI : 10.1109/IMCOM51814.2021.9377349
- ISBN : 9781665423182
- DBLP ID : conf/icuimc/ParqueM21
- SCOPUS ID : 85103740237