Maximum spanning forest

From Algowiki
Jump to: navigation, search

Input

  1. An undirected graph [math]G = (V,E)[/math], not necessarily connected.
  2. An edge length [math]l(e) \in \mathbb{R}[/math] for each edge [math]e \in E[/math].

Output

An undirected forest [math] F= (V,E_F)[/math] such that [math]E_F \subseteq E[/math].

Objective

Maximize: [math]\sum{}{}_{e \in E_F}l(e)[/math].

Complexity

Polynomial.

Known algorithms

Kruskal