論文

2021年

An Efficient Scheme for the Generation of Ordered Trees in Constant Amortized Time.

15th International Conference on Ubiquitous Information Management and Communication(IMCOM)
  • Victor Parque
  • ,
  • Tomoyuki Miyashita

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

エクスポート
BibTeX RIS