Cover Image

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Alaoui, Ziad Ismaili, Nakajima, Tamio-Vesa, Namrata, Wild, Sebastian
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Succinct Preferential Attachment Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Virtual-Memory Powersort
by: Moltmann, Finn, et al.
Published: (2026)

Implementing Binary Search Trees in GP 2 (Extended Abstract)
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Maximum And- vs. Even-SAT
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Towards Optimal Grammars for RNA Structures
by: Onokpasa, Evarista, et al.
Published: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

On the complexity of symmetric vs. functional PCSPs
by: Nakajima, Tamio-Vesa, et al.
Published: (2022)

Efficiency of ANS Entropy Encoders
by: Kosolobov, Dmitry
Published: (2022)

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)

Robust Gray Codes Approaching the Optimal Rate
by: Con, Roni, et al.
Published: (2024)

Succinct Graph Representations and Algorithmic Applications
by: Ullah, Ahammed, et al.
Published: (2026)

Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
by: Rao, Shravas
Published: (2023)

Graph Reconstruction from Noisy Random Subgraphs
by: McGregor, Andrew, et al.
Published: (2024)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
by: Guruswami, Venkatesan, et al.
Published: (2023)

On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
by: Wang, Ziao, et al.
Published: (2022)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
by: Wang, Ziao, et al.
Published: (2023)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
by: Bruno, Roberto, et al.
Published: (2025)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
by: Ciardo, Lorenzo, et al.
Published: (2023)

Efficient Rejection Sampling in the Entropy-Optimal Range
by: Draper, Thomas L., et al.
Published: (2025)

Asymptotically Optimal Sequential Testing with Heterogeneous LLMs
by: Li, Guokai, et al.
Published: (2026)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

Improved Explicit Near-Optimal Codes in the High-Noise Regimes
by: Li, Xin, et al.
Published: (2024)

Entropy Coding of Unordered Data Structures
by: Kunze, Julius, et al.
Published: (2024)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
by: Hammer, Nina, et al.
Published: (2022)

CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions
by: Coleman, Benjamin, et al.
Published: (2023)

Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
by: Li, Gen, et al.
Published: (2023)

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings
by: Elberfeld, Michael, et al.
Published: (2025)

A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
by: Wang, Xinzhao, et al.
Published: (2022)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

Succinct Planar Encoding with Minor Operations
by: Kammer, Frank, et al.
Published: (2023)

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)