A uniform paradigm to succinctly encode various families of trees

DOI10.1007/S00453-012-9664-0zbMath1286.68117OpenAlexW2051671786MaRDI QIDQ2441590

Arash Farzan, J. Ian Munro

Publication date: 25 March 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9664-0

zbMATH Keywords

treesordered treessuccinct data structuresunordered treescardinal treescompact encodingsentropy encoding

Mathematics Subject Classification ID

Trees (05C05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (21)

Succinct indices for path minimum, with applications ⋮ Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs ⋮ Simultaneous encodings for range and next/previous larger/smaller value queries ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ Representation of ordered trees with a given degree distribution ⋮ On the succinct representation of equivalence classes ⋮ Parallel construction of succinct trees ⋮ Encoding Nearest Larger Values ⋮ Succinct data structure for dynamic trees with faster queries ⋮ Encoding range minima and range top-2 queries ⋮ Encoding nearest larger values ⋮ Sorting and ranking of self-delimiting numbers with applications to tree isomorphism ⋮ Succinct data structures for nearest colored node in a tree ⋮ Unnamed Item ⋮ m-Bonsai: A Practical Compact Dynamic Trie ⋮ A framework for succinct labeled ordinal trees over large alphabets ⋮ Path queries on functions ⋮ Succinct data structures for bounded clique-width graphs ⋮ Unnamed Item ⋮ Compact representation of graphs of small clique-width ⋮ Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs

Cites Work

• Representing trees of higher degree
• Catalan, Motzkin, and Riordan numbers
• Binary trees having a given number of nodes with 0, 1, and 2 children
• Optimal bounds for the predecessor problem and related problems
• The number of trees
• Low Redundancy in Static Dictionaries with Constant Query Time
• Succinct ordinal trees with level-ancestor queries
• Compact Navigation and Distance Oracles for Graphs with Small Treewidth
• A Uniform Approach Towards Succinct Representation of Trees
• Dynamic Succinct Ordered Trees
• Universal Succinct Representations of Trees?
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Membership in Constant Time and Almost-Minimum Space
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Balanced parentheses strike back
• Succinct Ordinal Trees Based on Tree Covering
• Non-Associate Powers and a Functional Equation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A uniform paradigm to succinctly encode various families of trees