Sorry, you need to enable JavaScript to visit this website.

Succinct Data Structure for Path Graphs

Citation Author(s):
Girish Balakrishnan, Sankardeep Chakraborty, N S Narayanaswamy, Kunihiko Sadakane
Submitted by:
Girish Balakrishnan
Last updated:
2 March 2022 - 1:44am
Document Type:
Presentation Slides
Document Year:
Paper Code:

We consider the problem of designing space-efficient data structures for unlabelled path graphs with n vertices while supporting basic navigational queries such as degree, adjacency, and neighborhood queries efficiently. We provide two solutions for this problem. Our first data structure is succinct and occupies n log n+o(n log n) bits while answering adjacency query in O(log n) time, and neighborhood and degree queries in O(d log^2 n) time where d is the degree of the queried vertex. Our second data structure answers all these queries faster at the expense of slightly more space. More specifically, it consumes O(n log^2 n) bits while answering adjacency and degree queries in constant time and neighborhood query in O(d \log n) time. Central to our data structures is the usage of the classical heavy path decomposition, followed by a careful bookkeeping using an orthogonal range search data structure among others, which may be of independent interest for designing succinct data structures for other graphs.

0 users have voted: