P89: Generation of the $k$-th longest path in a tree

P89: Generation of the $k$-th longest path in a tree

Input:

A tree $T = (V, E)$ and an integer $k$.

Output:

The $k$-th longest path in $T$.

Complexity:

$O(n\log^2 n)$ time.

Comment:

Reference:

[Megiddo1981] (Bibtex)