4.3 Article

Succinct data structure for path graphs ☆

期刊

INFORMATION AND COMPUTATION
卷 296, 期 -, 页码 -

出版社

ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2023.105124

关键词

-

向作者/读者索取更多资源

This paper addresses the problem of designing a succinct data structure for path graphs and provides two solutions. The first solution supports adjacency, neighbourhood, and degree queries with time complexities of O(log n), O(d log n), and min{O(log2 n), O(d log n)} respectively. The second solution is a space-efficient data structure that optimally supports adjacency, neighbourhood, and degree queries.
We consider the problem of designing a succinct data structure for path graphs , that generalizes interval graphs, on n vertices while efficiently supporting degree, adjacency, and neighbourhood queries. We provide the following two solutions for this problem:1. an n log n + o(n log n)-bit succinct data structure that supports adjacency query in O (log n) time, neighbourhood query in O (d log n) time and finally, degree query in min{ O (log2 n), O (d log n)} time where d is the degree of the queried vertex.2. an O (n log2 n)-bit space-efficient data structure that supports adjacency, neighborhood, and degree queries optimally.Central to our data structures is the usage of the heavy path decomposition, followed by careful bookkeeping using an orthogonal range search data structure using wavelet trees among others, which may be of independent interest for designing succinct data structures for other graph classes.(c) 2023 Elsevier Inc. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据