Advanced search options

You searched for `id:"handle:10012/14520"`

. One record found.

▼ Search Limiters

University of Waterloo

1. Wu, Kaiyu. Succinct Data Structures for Chordal Graphs.

Degree: 2019, University of Waterloo

URL: http://hdl.handle.net/10012/14520

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) ∈ ω(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

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Wu, K. (2019). Succinct Data Structures for Chordal Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/14520

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

Wu, Kaiyu. “Succinct Data Structures for Chordal Graphs.” 2019. Thesis, University of Waterloo. Accessed April 22, 2019. http://hdl.handle.net/10012/14520.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Wu, Kaiyu. “Succinct Data Structures for Chordal Graphs.” 2019. Web. 22 Apr 2019.

Vancouver:

Wu K. Succinct Data Structures for Chordal Graphs. [Internet] [Thesis]. University of Waterloo; 2019. [cited 2019 Apr 22]. Available from: http://hdl.handle.net/10012/14520.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Wu K. Succinct Data Structures for Chordal Graphs. [Thesis]. University of Waterloo; 2019. Available from: http://hdl.handle.net/10012/14520

Not specified: Masters Thesis or Doctoral Dissertation