Sorting and ranking of self-delimiting numbers with applications to tree isomorphism

DOI10.1007/978-3-031-34347-6_30MaRDI QIDQ6182920zbMATH OpenFDO

Authors Frank Kammer, Johannes Meintrup, Andrej Sajenko

Publication date 22 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.07287

zbMATH Keywords

dense rankranksortingspace efficienttree isomorphism

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: 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(logN)$ bits. Our algorithms run in $O(k+fracNlogN)$ 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(nlogn)$ bits.

Cites work

• A constant-time colored choice dictionary with almost robust iteration
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• A uniform paradigm to succinctly encode various families of trees
• Comparison-based time-space lower bounds for selection
• Depth-First Search Using O(n) Bits
• Efficient Storage and Retrieval by Content and Address of Static Files
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Introduction to algorithms.
• Priority queues and sorting for read-only data
• Rank-select indices without tears
• Simple 2f-Color Choice Dictionaries
• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-efficient basic graph algorithms
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Space-efficient Euler partition and bipartite edge coloring
• Space-efficient vertex separators for treewidth
• Structural, Syntactic, and Statistical Pattern Recognition
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succinct representation of labeled graphs
• Upper bounds for time-space trade-offs in sorting and selection

This page was built for publication: Sorting and ranking of self-delimiting numbers with applications to tree isomorphism

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