论文标题
简洁的置换图
Succinct Permutation Graphs
论文作者
论文摘要
我们为排列图提供了简洁的数据结构及其圆形排列图的超类，即使用最佳空间到较低阶段的数据结构。与圆形图上的并发工作不同（Acan等，2022），我们的数据结构还支持距离和最短的路径查询，以及邻接和邻里查询，均在最佳时间内。我们特别提出了（圆形）置换图的第一个简洁的精确距离。第二个简洁的数据结构还支持时间查询，以额外的时间与邻里的大小无关，而牺牲了$ o（\ log n/\ log \ log \ log \ log n）$ - 因子在所有运行时间内开销。此外，我们为两部分排列图类别开发了简洁的数据结构。我们演示了如何直接通过简洁的表示算法来运行置换图上的几个问题：集团，着色，独立集，汉密尔顿周期，全对最短路径等。 最后，我们启动了半分布的图形表示的研究；一个在分布式（标记方案）和集中式（标准数据结构）之间平滑插值的概念。我们展示了如何通过仅存储$ o（n）$位的其他全局信息来将我们的某些数据结构转换为半分布的表示形式，从而规避置换图的距离标记方案的下限。
We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an $O(\log n/\log \log n)$-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only $O(n)$ bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.
