Maximum spanning forest

From Algowiki
Revision as of 20:01, 6 October 2014 by Dkratschmann (talk | contribs)
Jump to navigation Jump to search

Input

  1. An undirected graph [math]\displaystyle{ G = (V,E) }[/math], not necessarily connected.
  2. An edge length [math]\displaystyle{ l(e) \in \mathbb{R}_0^+ }[/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.

Known algorithms

Kruskal

Known variants

Remark