论文标题
与外平面图应用程序的分类和排名
Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
论文作者
论文摘要
假设$ n $ bit序列$ s的$ s $ $ k $数字编码为Elias Gamma代码作为输入。我们提出了用于排序，密集排名和竞争性排名的空间算法，该算法在$ s $中，单词大小$ω（\ log n）$位。我们的算法以$ o（k + \ frac {n} {\ log n}）$时间运行，并使用$ o（n）$ bits。排序算法以排序顺序返回给定数字，存储在$ n $位的比特矢量中，而我们的排名算法构建了数据结构，这些数据结构使我们随后能够在固定时间内返回$ s $中每个数字$ x $的密集/竞争等级。对于数字$ x \ in \ mathbb {n} $带有$ x> n $的$，我们需要$ x $的位置$ p_x $作为我们的密度 - /竞争量表数据结构的输入。作为上述算法的应用，我们给出了树皮同构算法，该算法以$ o（n）$时间运行，并在$ n $ node树上使用$ o（n）$ lits。最后，我们将树皮同构的结果推广到森林和外平面图，同时保持$ o（n）$位的空间用途。以前的最佳树木，森林和外平面图同构的最佳线性时间算法都使用$θ（n \ log n）$位。
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.
