2026-08-11T21:31:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10015 2024-03-06T10:45:20Z ddc:004 open_access

Succinct Data Structures for Chordal Graphs Munro, J. Ian Wu, Kaiyu Succinct Data Structure Chordal Graph 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 Schloss Dagstuhl – Leibniz-Zentrum für Informatik J. Ian Munro and Kaiyu Wu 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.67 urn:nbn:de:0030-drops-100153 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.67 eng https://creativecommons.org/licenses/by/3.0/legalcode