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