Maximum branching: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 10: | Line 10: | ||
'''Output:''' | '''Output:''' | ||
A branching <math>B=(V,A')</math> of maximum weight such that <math>A'\subseteq A</math>. In that, the weight of a branching is the sum of the weights of all arcs in <math>A'</math>. | A branching <math>B=(V,A')</math> of maximum weight such that <math>A'\subseteq A</math>. In that, the weight of a branching is the sum of the weights of all arcs in <math>A'</math>. | ||
== Known algorithms== | |||
# 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. | |||
Revision as of 08:56, 11 October 2014
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 [math]\displaystyle{ B=(V,A') }[/math] of maximum weight such that [math]\displaystyle{ A'\subseteq A }[/math]. In that, the weight of a branching is the sum of the weights of all arcs in [math]\displaystyle{ A' }[/math].
Known algorithms
- 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.