Succinct data structure for path graphs

DOI10.1016/J.IC.2023.105124MaRDI QIDQ6178455zbMATH OpenFDO

Authors Girish Balakrishnan, Sankardeep Chakraborty, N. S. Narayanaswamy, Kunihiko Sadakane

Publication date 18 January 2024

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.04332

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We consider the problem of designing a succinct data structure for {it path graphs} (which are a proper subclass of chordal graphs and a proper superclass of interval graphs) on $n$ vertices while supporting degree, adjacency, and neighborhood queries efficiently. We provide the following two solutions for this problem: - an $nlogn+o(nlogn)$-bit succinct data structure that supports adjacency query in $O(logn)$ time, neighborhood query in $O(dlogn)$ time and finally, degree query in $minO(lo{g}^{2}n),O(dlogn)$ where $d$ is the degree of the queried vertex. - an $O(nlo{g}^{2}n)$-bit space-efficient data structure that supports adjacency and degree queries in $O(1)$ time, and the neighborhood query in $O(d)$ time where $d$ is the degree of the queried vertex. Central to our data structures is the usage of the classical heavy path decomposition by Sleator and Tarjan~cite{ST}, followed by a careful bookkeeping using an orthogonal range search data structure using wavelet trees~cite{Makinen2007} among others, which maybe of independent interest for designing succinct data structures for other graph classes.

Cites work

• A recognition algorithm for the total graphs
• Algorithmic graph theory and perfect graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Clique-width and the speed of hereditary properties
• Compact navigation and distance oracles for graphs with small treewidth
• Compact representation of graphs with bounded bandwidth or treedepth
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• Fast breadth-first search in still less space
• Fully functional static and dynamic succinct trees
• Graph theory
• scientific article; zbMATH DE number 2044924 (Why is no real title available?)
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Indexing graph search trees and applications
• Intersection graphs of paths in a tree
• Intersection representations of graphs by arcs
• Introduction to algorithms.
• Rank and select revisited and extended
• Rank/select operations on large alphabets
• Space efficient linear time algorithms for BFS, DFS and applications
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Succinct data structures for chordal graphs
• Succinct data structures for families of interval graphs
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Succinct encoding of arbitrary graphs
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct navigational oracles for families of intersection graphs on a circle
• Succinct representation for (non)deterministic finite automata
• Succinct representation of balanced parentheses and static trees
• Succinct representation of labeled graphs
• Succinct representations of planar maps

Cited in

(2)

• Succinct data structure for chordal graphs with bounded vertex leafage
• Succinct data structures for chordal graph with bounded leafage or vertex leafage

This page was built for publication: Succinct data structure for path graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178455)