https://wiki.algo.informatik.tu-darmstadt.de/index.php?action=history&feed=atom&title=Minimum_spanning_tree
Minimum spanning tree - Revision history
2026-05-28T20:59:19Z
Revision history for this page on the wiki
MediaWiki 1.38.4
https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Minimum_spanning_tree&diff=3311&oldid=prev
Weihe: Created page with "== Input == # An undirected graph <math>G = (V,E)</math>, not necessarily connected. # An edge length <math>l(e) \in..."
2015-06-16T12:33:01Z
<p>Created page with "== Input == # An <a href="/Basic_graph_definitions#Directed_and_undirected_graphs" title="Basic graph definitions">undirected graph</a> <math>G = (V,E)</math>, not necessarily connected. # An edge length <math>l(e) \in..."</p>
<p><b>New page</b></p><div>== Input ==<br />
# An [[Basic graph definitions#Directed and undirected graphs|undirected graph]] <math>G = (V,E)</math>, not necessarily connected.<br />
# An edge length <math>l(e) \in \mathbb{R}_0^+</math> for each edge <math>e \in E</math>.<br />
<br />
== Output ==<br />
An [[Basic graph definitions#Forests, trees, branchings, arborescences|undirected tree]] <math> T= (V,E_F)</math> such that <math>E_T \subseteq E</math>.<br />
<br />
== Objective ==<br />
<br />
'''Minimize:''' <math>\sum{}{}_{e \in E_F}l(e)</math>.<br />
<br />
== Complexity ==<br />
<br />
Polynomial.<br />
<br />
== Known algorithms ==<br />
<br />
[[Prim]]</div>
Weihe