The decompressed tree size of $k$-ary chains
A chain is defined as a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree computed using a depth-first search is a path. Such DAGs emerge in the context of tree compression and are therefore uniquely associated with a tree. The tree size of a DAG is defined as the size of the associated tree. For fixed out-degree $k \geq 2$, we compute the asymptotic expected decompressed tree size of a chain of size $n$ chosen uniformly at random, and we show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. This…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.18617
curl -X POST /api/v1/records/arxiv/2604.18617/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.18617/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'