Documents
Presentation Slides
Succinct Data Structure for Path Graphs
- Citation Author(s):
- Submitted by:
- Girish Balakrishnan
- Last updated:
- 2 March 2022 - 1:44am
- Document Type:
- Presentation Slides
- Document Year:
- 2022
- Event:
- Presenters:
- GIRISH BALAKRISHNAN
- Paper Code:
- 201
- Categories:
- Keywords:
- Log in to post comments
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.