Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913488612360192 |
|---|---|
| author | Kammer, Frank Meintrup, Johannes Sajenko, Andrej |
| author_facet | Kammer, Frank Meintrup, Johannes Sajenko, Andrej |
| contents | Assume that an $N$-bit sequence $S$ of $k$ numbers encoded as Elias gamma codes is given as input. We present space-efficient algorithms for sorting, dense ranking and competitive ranking on $S$ in the word RAM model with word size $Ω(\log N)$ bits. Our algorithms run in $O(k + \frac{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/competitive rank of each number $x$ in $S$ in constant time. For numbers $x \in \mathbb{N}$ with $x > N$ we require the position $p_x$ of $x$ as the input for our dense-/competitive-rank data structure. As an application of our algorithms above we give an algorithm for tree isomorphism, which runs in $O(n)$ time and uses $O(n)$ bits on $n$-node trees. Finally, we generalize our result for tree isomorphism to forests and outerplanar graphs, while maintaining a space-usage of $O(n)$ bits. The previous best linear-time algorithms for trees, forests and outerplanar graph isomorphism all use $Θ(n \log n)$ bits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2002_07287 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism Kammer, Frank Meintrup, Johannes Sajenko, Andrej Data Structures and Algorithms F.2.2 Assume that an $N$-bit sequence $S$ of $k$ numbers encoded as Elias gamma codes is given as input. We present space-efficient algorithms for sorting, dense ranking and competitive ranking on $S$ in the word RAM model with word size $Ω(\log N)$ bits. Our algorithms run in $O(k + \frac{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/competitive rank of each number $x$ in $S$ in constant time. For numbers $x \in \mathbb{N}$ with $x > N$ we require the position $p_x$ of $x$ as the input for our dense-/competitive-rank data structure. As an application of our algorithms above we give an algorithm for tree isomorphism, which runs in $O(n)$ time and uses $O(n)$ bits on $n$-node trees. Finally, we generalize our result for tree isomorphism to forests and outerplanar graphs, while maintaining a space-usage of $O(n)$ bits. The previous best linear-time algorithms for trees, forests and outerplanar graph isomorphism all use $Θ(n \log n)$ bits. |
| title | Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2002.07287 |