Maximum spanning forest: Difference between revisions
Jump to navigation
Jump to search
Dkratschmann (talk | contribs) (Created page with "== Input == # An undirected graph <math>G = (V,E)</math>, not necessarily connected. # An edge length <math>l(e) \in \mathbb{R}_0^+</math> for each edge <math>e \in E</mat...") |
(→Input) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Input == | == Input == | ||
# An [[undirected graph]] <math>G = (V,E)</math>, not necessarily connected. | # An [[Basic graph definitions#Directed and undirected graphs|undirected graph]] <math>G = (V,E)</math>, not necessarily connected. | ||
# An edge length <math>l(e) \in \mathbb{R} | # An edge length <math>l(e) \in \mathbb{R}</math> for each edge <math>e \in E</math>. | ||
== Output == | == Output == | ||
An [[undirected forest]] <math> F= (V,E_F)</math> such that <math>E_F \subseteq E</math>. | An [[Basic graph definitions#Forests, trees, branchings, arborescences|undirected forest]] <math> F= (V,E_F)</math> such that <math>E_F \subseteq E</math>. | ||
== Objective == | == Objective == | ||
| Line 12: | Line 12: | ||
== Complexity == | == Complexity == | ||
Polynomial | Polynomial. | ||
== Known algorithms == | == Known algorithms == | ||
[[Kruskal]] | [[Kruskal]] | ||
Latest revision as of 18:03, 18 September 2015
Input
- An undirected graph [math]\displaystyle{ G = (V,E) }[/math], not necessarily connected.
- An edge length [math]\displaystyle{ l(e) \in \mathbb{R} }[/math] for each edge [math]\displaystyle{ e \in E }[/math].
Output
An undirected forest [math]\displaystyle{ F= (V,E_F) }[/math] such that [math]\displaystyle{ E_F \subseteq E }[/math].
Objective
Maximize: [math]\displaystyle{ \sum{}{}_{e \in E_F}l(e) }[/math].
Complexity
Polynomial.