Mahdi Amani (Università di Pisa, Pisa, Italy) |
Abbas Nowzari-Dalini (UT, Tehran, Iran) |

We study the problem of generating, ranking and unranking of unlabeled ordered trees whose nodes have maximum degree of Δ. This class of trees represents a generalization of chemical trees. A chemical tree is an unlabeled tree in which no node has degree greater than 4. By allowing up to Δ children for each node of chemical tree instead of 4, we will have a generalization of chemical trees. Here, we introduce a new encoding over an alphabet of size 4 for representing unlabeled ordered trees with maximum degree of Δ. We use this encoding for generating these trees in A-order with constant average time and O(n) worst case time. Due to the given encoding, with a precomputation of size and time O(n^2) (assuming Δ is constant), both ranking and unranking algorithms are also designed taking O(n) and O(nlogn) time complexities. |

Published: 2nd March 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.204.4 | bibtex | |

Comments and questions to: eptcs@eptcs.org |

For website issues: webmaster@eptcs.org |