Maximum branching: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== General information == '''Definition:''' A '''branching''' is a cycle-free '''Input:''' # A directed graph <math>G=(V,A)</math>: # A real-valued weight <math>w(a)</math>...") |
|||
| (11 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== | == Basic definitions == | ||
# [[Basic graph definitions]] | |||
== General information == | |||
'''Input:''' | '''Input:''' | ||
# A directed graph <math>G=(V,A)</math>: | # A directed graph <math>G=(V,A)</math>: | ||
# A real-valued weight <math> | # A real-valued weight <math>x(a)</math> for each arc <math>a\in A</math>. | ||
'''Output:''' | |||
A [[Basic graph definitions#Forests, trees, branchings, arborescences|branching]] <math>B=(V,A')</math> of maximum weight such that <math>A'\subseteq A</math>. In that, the '''weight''' of <math>B</math> 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. | |||
Latest revision as of 07:53, 8 November 2015
Basic definitions
General information
Input:
- A directed graph [math]\displaystyle{ G=(V,A) }[/math]:
- 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
Remark
Without loss of generality, all arcs with nonpositive weights may be removed, so we may assume that all weights are strictly positive.