Master’s Thesis Presentation • Algorithms and Complexity — Succinct Data Structures for Chordal Graphs

Kaiyu (Kevin) Wu, Master’s candidate
David R. Cheriton School of Computer Science

We study the problem of approximate shortest path queries in chordal graphs and give a $n\log n + o(n\log n)$ bit data structure to answer the approximate distance query to within an additive constant of 1 in $O(1)$ time.

We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let $G$ be a chordal graph with $n$ vertices. We design a data structure using the information theoretic minimal $n^2/4 + o(n^2)$ bits of space to support the queries:

• whether two vertices $u,v$ are adjacent in time $f(n)$ for any $f(n) \in \omega(1)$
• the degree of a vertex in $O(1)$ time
• the vertices adjacent to $u$ in $(f(n))^2$ time per neighbour
• the length of the shortest path from $u$ to $v$ in $O(nf(n))$ time