Tossup

Gabriel Nivasch’s “multi-stack” algorithm identifies these structures. An unsolved problem that asks whether these structures produce a double cover reduces to asking about “snarks.” These structures cause Kahn’s algorithm to output an empty list, since they prevent topological sortings. (10[1])Pollard’s algorithm for integer factorization is named for the eventual resemblance to one of these structures over time. Gosper’s algorithm for detecting these structures improves upon another algorithm that creates a leading and trailing pointer called a “hare” and “tortoise” and is named for Floyd. Detecting these structures by checking already-visited nodes ensures that DFS halts. The [emphasize] absence (10[1])of these structures defines the “A” in a DAG. (10[1])For 10 points, name these paths in a graph that eventually lead back to their start. ■END■ (10[3])

Back to tossups

Buzzes

Summary