We design succinct encodings of {\it series-parallel, block-cactus} and {\it 3-leaf power} graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood {\it optimally} in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds.
翻译：我们设计了 ~it 系列单词、 区块- cactus} 和 ~it 3-leaf power} 图形的简明编码,同时用对数字大小支持 RAM 模型中的基本导航查询, 如度、 相邻度和相邻度 。 我们所代表的一个突出特征是, 即使这些图形类的准确空间较低, 但它仍然可以达到最佳的空间。 对于这些图形类, 我们第一次在文献中提供最优查询支持的简明数据结构 。 对于 系列平行多面图, 我们的工作还扩展了 Uno 等人的作品( Disc. Math. Alg and Appl., 2013) 和 Bleloch and Farzan (CPM, 2010) 以产生最佳界限 。
相关内容
微信扫码咨询专知VIP会员