arXiv preprint ·
Succinct Representation of Search Trees on Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
The Complexity of Computing Class Probabilities in BID Probabilistic Databases
Union-Find with Constant-Time Deletions Across the Optimal Worst-Case Tradeoff
A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees
Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.