Maximum branching: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Basic definitions ==
# [[Basic graph definitions]]
== General information ==
== General information ==
'''Definition:'''
A '''branching''' is a [[Basic graph definitions|cycle-free directed graph]] such that each node has at most one incoming arc.


'''Input:'''
'''Input:'''
# A directed graph <math>G=(V,A)</math>:
# A directed graph <math>G=(V,A)</math>:
# A real-valued weight <math>w(a)</math> for each arc <math>a\in A</math>.
# A real-valued weight <math>x(a)</math> for each arc <math>a\in A</math>.


'''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 of its arcs.
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

  1. Basic graph definitions

General information

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.