= Reverse-delete algorithm
{wiki}
= Reverse Kruskal algorithm
{synonym}
Process <edges> in decreasing weight and delete an <edge> whenever the remaining <graph> stays connected. Previously retained heavier <edges> are <bridges in a graph> and remain so under deletion. Thus a deletable <edge> is heaviest on a current <graph cycle>, and the <minimum spanning tree cycle property> excludes it from every <minimum spanning tree>. At termination the surviving connected <graph> has no <graph cycle>, so it is a <minimum spanning tree>.
Back to article page
