PhD Seminar • Algorithms and Complexity • Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct TreesExport this event to calendar

Wednesday, February 1, 2023 — 2:00 PM to 3:00 PM EST

Please note: This PhD seminar will take place in DC 1304 and virtually over Zoom.

Kaiyu (Kevin) Wu, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor J. Ian Munro

We present succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports the mapping between preorder (i.e., depth-first) ranks and level-order (breadth-first) ranks of nodes in constant time.

Our distance oracles for interval graphs also support navigation queries — testing adjacency, computing node degrees, neighborhoods, and shortest paths — all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well as mapping to and from level-order ranks and retrieving the last (first) internal node before (after) a given node in a level-order traversal, all in constant time.


To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/99019598246.

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
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
29
30
31
1
2
3
4
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)