Succinct representation of labeled trees
From MaRDI portal
Publication:476876
DOI10.1016/J.TCS.2014.10.006zbMATH Open1303.68043arXiv1312.6039OpenAlexW2053769163MaRDI QIDQ476876FDOQ476876
Authors: Dekel Tsur 
Publication date: 2 December 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: We give a representation for labeled ordered trees that supports labeled queries such as finding the i-th ancestor of a node with a given label. Our representation is succinct, namely the redundancy is small-o of the optimal space for storing the tree. This improves the representation of He et al. which is succinct unless the entropy of the labels is small.
Full work available at URL: https://arxiv.org/abs/1312.6039
Recommendations
Cites Work
- Succinct representation of balanced parentheses and static trees
- Fully functional static and dynamic succinct trees
- New lower and upper bounds for representing sequences
- Succinct ordinal trees with level-ancestor queries
- Compressing and indexing labeled trees, with applications
- Representing trees of higher degree
- Adaptive searching in succinctly encoded binary relations and tree-structured documents
- Succinct representations of permutations and functions
- Orderly Spanning Trees with Applications
- A Uniform Approach Towards Succinct Representation of Trees
- A Framework for Succinct Labeled Ordinal Trees over Large Alphabets
Cited In (16)
- Reduced representations of rooted trees.
- LATIN 2004: Theoretical Informatics
- A uniform paradigm to succinctly encode various families of trees
- Tradeoff between label space and auxiliary space for representation of equivalence classes
- Short Labels by Traversal and Jumping
- Representation of ordered trees with a given degree distribution
- Short Transitive Signatures for Directed Trees
- Succinct representation of labeled graphs
- Title not available (Why is that?)
- A framework for succinct labeled ordinal trees over large alphabets
- Tree path majority data structures
- A Uniform Approach Towards Succinct Representation of Trees
- Succinct data structures for nearest colored node in a tree
- Succinct data structure for dynamic trees with faster queries
- Succinct Representation of Labeled Graphs
- Path queries on functions
This page was built for publication: Succinct representation of labeled trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476876)
