Maximum branching

Basic definitions

1. Basic graph definitions

General information

Definition: A branching is an acyclic directed graph such that each node has at most one incoming arc.

Input:

1. A directed graph [math]\displaystyle{ G=(V,A) }[/math]:
2. A real-valued weight [math]\displaystyle{ x(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].

Output: A branching [math]\displaystyle{ B=(V,A') }[/math] of maximum weight such that [math]\displaystyle{ A'\subseteq A }[/math]. In that, the weight of [math]\displaystyle{ B }[/math] is the sum of the weights of all arcs in [math]\displaystyle{ A' }[/math].

Known algorithms

1. Branching by Edmonds

Remark

Without loss of generality, all arcs with nonpositive weights may be removed, so we may assume that all weights are strictly positive.