Ranking and unranking trees with given degree sequences

Details Ranking and unranking trees with given degree sequences Ranking and unranking trees with given degree sequences

2010-09-10

arxiv.org/abs/1009.2059v1

Mathematics

Combinatorics

Scientific paper

In this paper, we provide algorithms to rank, unrank, and randomly generate certain degree-restricted classes of Cayley trees. Specifically, we consider classes of trees that have a given degree sequence or a given multiset of degrees. If the underlying set of trees have n vertices, then the largest ranks involved in each case are of order n! so that it takes O(nlog(n)) bits just to write down the ranks. Our ranking and unranking algorithms for these degree-restricted classes are as efficient as can be expected since we show that they require O(n^2log(n)) bit operations if the underlying trees have n vertices.

Affiliated with

Also associated with

No associations

Rating

Ranking and unranking trees with given degree sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ranking and unranking trees with given degree sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ranking and unranking trees with given degree sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-672739