Back to search

University of Waterloo

Succinct Data Structures for Chordal Graphs

Abstract

dc:description.abstract

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 O(f(n)^2) time per neighbour the length of the shortest path from u to v in O(n f(n)) time

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wu, Kaiyu
Advisor dc:contributor.advisor
  • Munro, J. Ian

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/14520

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wu, Kaiyu. Succinct Data Structures for Chordal Graphs. University of Waterloo, 2019. http://hdl.handle.net/10012/14520