Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"handle:10012/14520". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Waterloo

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

Degree: 2019, University of Waterloo

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 n2/4 + o(n2) 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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.