Improved algorithms for ranking and unranking (k, m)-ary trees in B-order

DOI10.1007/S10878-019-00469-ZMaRDI QIDQ2082174zbMATH OpenOpenAlexWikidataFDO

Authors Yu-Hsuan Chang, Ro-Yu Wu, Ruay-Shiung Chang, Jou-Ming Chang

Publication date 4 October 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-019-00469-z

zbMATH Keywords

\((k, m)\)-ary treesamortized costlexicographic/reverse-lexicographic orderranking/unranking algorithmsRD-sequencesZaks' sequences

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Algorithms on strings (68W32)

Recommendations

• Efficient generation, ranking, and unranking of \((k,m)\)-ary trees in B-order
• Ranking and unrankingk-ary trees with a 4k –4 letter alphabet
• Lexicographic Enumeration of k-ary Trees
• Generating t-ary trees in A-order
• Ranking and unranking algorithms for loopless generation of t-ary trees

Cites work

• \((k,m)\)-Catalan numbers and hook length polynomials for plane trees
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• A new algorithm for generation of different types of RNA
• Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order
• Efficient generation, ranking, and unranking of \((k,m)\)-ary trees in B-order
• Gap terminology and related combinatorial properties for AVL trees and Fibonacci-isomorphic trees
• Generating trees withnnodes andmleaves
• Generation, ranking and unranking of ordered trees with degree bounds
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 6985563 (Why is no real title available?)
• Lexicographic generation of ordered trees
• Ranking and Unranking of AVL-Trees
• Ranking and unranking of non-regular trees with a prescribed branching sequence

Cited in

(4)

• Algorithms for generalized vertex-rankings of partial k-trees
• Algorithms for improving the quality of \(R\)-trees
• Efficient generation, ranking, and unranking of \((k,m)\)-ary trees in B-order
• Improved algorithms for ranking and unranking \((k, m)\)-ary trees

This page was built for publication: Improved algorithms for ranking and unranking \((k, m)\)-ary trees in B-order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2082174)