Maximum branching: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 9: Line 9:


'''Output:'''
'''Output:'''
A branching of maximum weight such that all arcs in the branching are arcs of <math>G</math>. In that, the weight of a branching is the sum of the weights of all of its arcs.
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 of its arcs.

Revision as of 08:54, 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:

  1. A directed graph [math]\displaystyle{ G=(V,A) }[/math]:
  2. 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 of its arcs.