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 \Omega(\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  .
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 \Omega(\log N) bits . 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 allow 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 , which runs in O(n) time and uses O(n) bits on n-node trees . The previous best linear-time algorithm for tree isomorphism uses \Theta(n \log n) bits .
A
bits
A
,
A
,
R
allows
allow
R
that
, which
A
. The previous best linear-time algorithm for tree isomorphism uses \Theta(n \log n) bits