202502181602

Tags : Verification of MST, Topics in Algorithms

Special Case of Tree Path Maxima Problem

---

The Tree Path Maxima Problem is defined as follows:

Question

Given a tree $T$ with real edge weights and a list of pairs of distinct nodes in $T$, determine for each pair $(u,v)$ on the list, a heaviest path edge on the path from $u$ to $v$ in $T$.

Link to original

The special case adds 2 restrictions to the problem:

• The tree is a fully-branching tree which is a rooted tree with all leaves at the same depth and all inner nodes have at least 2 children.
• For each pair $(u,v)$ we have that $u\ne v$ and $u$ is an ancestor of $v$.

---

References