Maximum branching
General information
Definition: A branching is a cycle-free directed graph such that each node has at most one incoming arc.
Input:
- A directed graph [math]\displaystyle{ G=(V,A) }[/math]:
- A real-valued weight [math]\displaystyle{ w(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].
Output: A branching of maximum weight such that all arcs in the branching are arcs of [math]\displaystyle{ G }[/math]. In that, the weight of a branching is the sum of the weights of all of its arcs.