Succinct Preferential Attachment Graphs
summary
Claims a static rooted binary tree topology encodes in 2n bits plus o(n) and supports constant‑time navigation and subtree queries by grouping nodes into microtrees of size Θ(log n), Huffman‑coding the microtree shapes to achieve instance‑optimal (log 1/Pr) space for many distributions. For graphs, the simple scheme concatenating adjacency lists and zeroth‑order compression is optimal for the preferential‑attachment (Barabási‑Albert) model; uses wavelet trees to support rank/select queries, and converts labeled m‑out graphs to an implicit tree to avoid storing labels.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:08Motivation for succinct structures
- 2:12Optimal compression and self-information
- 7:42Optimal tree compression
- 10:37Why graphs harder to compress
- 18:33Simple graph compression with in-degree entropy
- 19:57Preferential-attachment model
- 23:08Storing unlabeled PA graphs
- 25:17Summary
- 26:24Q&A
related talks
29mSpotting Trees with Few Leaves
38mLower Bounds on the Space Complexity of Dynamic Programming
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
23mWorst-Case to Expander-Case Reductions
01h 02mFine-Grained Counting Complexity II
01h 02mFine-Grained Counting Complexity I
29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
29mColor Coding-Related Techniques