PhD Seminar • Algorithms and Complexity • Shortest Beer Path Queries in Interval GraphsExport this event to calendar

Friday, December 2, 2022 — 2:00 PM to 3:00 PM EST

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 O(nO(|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 3o(n) bits to support beer distance queries in O(f(nlog 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.

Paper link: https://arxiv.org/abs/2209.14401


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/96257315410. You can also attend in person in DC 1304.

Location 
DC - William G. Davis Computer Research Centre
Hybrid: DC 1304 | Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
  1. 2023 (33)
    1. March (1)
    2. February (10)
    3. January (22)
  2. 2022 (245)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (12)
    5. August (29)
    6. July (23)
    7. June (17)
    8. May (20)
    9. April (24)
    10. March (22)
    11. February (16)
    12. January (19)
  3. 2021 (210)
  4. 2020 (217)
  5. 2019 (255)
  6. 2018 (217)
  7. 2017 (36)
  8. 2016 (21)
  9. 2015 (36)
  10. 2014 (33)
  11. 2013 (23)
  12. 2012 (4)
  13. 2011 (1)
  14. 2010 (1)
  15. 2009 (1)
  16. 2008 (1)