Question

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 (15[1])minus two” of these constructs in a (-5[1])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 (-5[1])10 points, name these acyclic structures that connect all vertices of a (10[1]0[1])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

Back to tossups

Buzzes

PlayerTeamOpponentBuzz PositionValue
David BassJHU AColumbia6815
Eshan PantNYU APrinceton75-5
Kevin LiuMarylandJHU B117-5
Derrick LiuJHU BMaryland1290
Lucas ShedlockPrincetonNYU A12910

Summary

2024 Penn Bowl UNC10/26/2024Y367%33%0%66.50
2024 Penn Bowl Florida10/26/2024Y2100%100%0%63.50
2024 Penn Bowl Harvard10/26/2024Y475%25%75%101.33
2024 Penn Bowl UK10/26/2024Y5100%60%20%79.00
2024 Penn Bowl Berkeley11/02/2024Y2100%100%0%46.50
2024 Penn Bowl Mainsite11/02/2024Y367%33%67%98.50
2024 Penn Bowl CWRU11/02/2024Y450%25%25%69.50
2024 Penn Bowl Chicago11/02/2024Y863%25%25%77.00
2024 Penn Bowl Texas11/02/2024Y250%0%0%101.00