Please note: This PhD seminar will take place in DC 3317.
Kaiyu
(Kevin)
Wu,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
Supervisor: Professor J. Ian Munro
We enhance several data structures for intersection graphs. The data structures of Chakraborty and Jo for bounded degree and bounded chromatic number interval graphs, Balakrishnan et al. We show that both bounded degree and bounded chromatic number interval graphs have a tight lower bound of $n\log \sigma$ (lower order terms omitted) bits where $\sigma$ is the maximum degree or chromatic number of the graph. This improves the lower bound of Chakraborty and Jo from $\frac{1}{6}n\log\sigma$.
For bounded chromatic number interval graphs, we give a $n\log \sigma$ bit space succinct data structure with $O(\sigma\log n)$ query times. To match the time complexity of $O(\log\log\sigma)$ we use $2n\log\sigma$ bits rather than $(\sigma -1)n$ bits.
For path graphs, we give a succinct $n\log n$ bit data structure with query times $O(\frac{\log n}{\log\log n})$ rather than $O(\log^2 n)$ of Balakrishnan et al. To achieve $O(1)$ query times, we give a data structure using $(2+\varepsilon)n\log n$ bits rather than $O(n\log^2 n)$ bits.