An algorithm for finding these things with provably optimal but unknown runtime was developed by Pettie and Ramachandran. Another algorithm for finding these things that features an inverse Ackermann function in its complexity analysis prompted Bernard Chazelle to develop the soft heap. For any cut, the crossing edge with the lowest weight is part of one of these things. There are [read slowly] “n to the power of n minus two” of these constructs in a complete graph according to (*) Cayley’s theorem. The edge with the lowest weight that does not form a cycle is iteratively removed in one algorithm for finding these things. The “minimum” form of these things is outputted by Prim’s and Kruskal’s algorithms. For 10 points, name these acyclic structures that connect all vertices of a graph. ■END■
ANSWER: minimum spanning trees [accept MST; accept forest in place of “tree”; prompt on forests; prompt on trees]
<Alex Li, Other Science>
= Average correct buzz position