Low-Cost Arborescence Under Edge Faults

Dipan Dey, Telikepalli Kavitha

Our input is a directed graph $G=(V,E)$ on $n$ vertices and $m$ edges with a designated root vertex $r$ and a function $cost:E\to {\mathbb{R}}_{\ge 0}$. The problem is t…