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 l´Ç²µÌý²ÔÌý+ÌýO(n)Ìý+ÌýO(|B|l´Ç²µÌý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 3²ÔÌý+Ìýo(n) bits to support beer distance queries in O(f(n)Ìýl´Ç²µÌý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)²ÔÌý−Ìýo(n) (or about 2.9n) bits.