Please note: This PhD seminar will take place in DC 1304 and online.
Kevin Wu, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Ian Munro
Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path.
We show that we can represent unweighted interval graphs using 2n log n + O(n) + O(|B|log n) bits where |B| is the number of beer vertices. This data structure answers beer distance queries in O(logε n) time for any constant ε > 0 and shortest beer path queries in O(logε n+d) time, where d is the beer distance between the two nodes. We also show that proper interval graphs may be represented using 3n + o(n) bits to support beer distance queries in O(f(n) log n) time for any f(n) ∈ ω(1) and shortest beer path queries in O(d) time. All of these results also have time-space trade-offs.
Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely log(4+2√3)n − o(n) (or about 2.9n) bits.