Sorting and Ranking of Self-Delimiting Numbers with Applications to Tree Isomorphism
share
Assume that an N-bit sequence S of k self-delimiting numbers is given as input. We present space-efficient algorithms for sorting, dense ranking and (competitive) ranking S on the word RAM model with word size Ω(log N). Our algorithms run in O(k + N/log N) time and use O(N) bits. The sorting algorithm returns the given numbers in sorted order stored within a bit-vector of N bits whereas our ranking algorithms construct data structures that allows us subsequently to return the (dense) rank of each number x in S in constant time if the position of x in S is given together with x. As an application of our algorithms we give an algorithm for tree isomorphism that runs in O(n) time and uses O(n) bits on n-node trees.
READ FULL TEXT