Master’s Thesis Presentation • Algorithms and Complexity — Succinct Data Structures for Chordal GraphsExport this event to calendar

Wednesday, March 20, 2019 1:30 PM EDT

Kaiyu (Kevin) Wu, Master’s candidate
David R. Cheriton School of Computer Science

We study the problem of approximate shortest path queries in chordal graphs and give a $n\log n + o(n\log n)$ bit data structure to answer the approximate distance query to within an additive constant of 1 in $O(1)$ time.

We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let $G$ be a chordal graph with $n$ vertices. We design a data structure using the information theoretic minimal $n^2/4 + o(n^2)$ bits of space to support the queries:

  • whether two vertices $u,v$ are adjacent in time $f(n)$ for any $f(n) \in \omega(1)$
  • the degree of a vertex in $O(1)$ time
  • the vertices adjacent to $u$ in $(f(n))^2$ time per neighbour
  • the length of the shortest path from $u$ to $v$ in $O(nf(n))$ time
Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

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
29
30
1
2
  1. 2024 (96)
    1. April (19)
    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)