The Distribution Function of the Longest Path Length in Constant Treewidth DAGs with Random Edge Length

Ei Ando

This paper is about the length $X_{\mathrm{MAX}}$ of the longest path in directed acyclic graph (DAG) $G=(V,E)$ with random edge lengths, where $|V|=n$ and $|E|=m$. When the edge length…