<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(k \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(e^{c \, \sqrt{n}}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>e</mi> <mrow> <mi>c</mi> <mspace width="0.166667em" /> <msqrt> <mi>n</mi> </msqrt> </mrow> </msup> </math></EquationSource> </InlineEquation>. This result also has implications for the limit distribution of Brauer chains of fixed length.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Decompressed Tree Size of k-Ary Chains

  • Michael Wallner

摘要

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 \ge 2\) k 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}}\) e c n . This result also has implications for the limit distribution of Brauer chains of fixed length.