Question
A breakthrough 2009 Bender et al. paper presents an algorithm for continually performing this task that explicitly avoids tracking affected regions. Purdom’s algorithm for finding transitive closures achieves quadratic time by precomputing the result of this task. A method for determining rank ordering in a round-robin tournament that minimizes upsets relies on performing this task on the feedback arc set of the tournament. The reverse of a postorder depth-first search’s iteration order is a solution to this task. (*) Kahn’s algorithm for this task repeatedly finds a source node, removes it from the graph, and appends it to a running list; source nodes must always exist since this task is only defined for directed acyclic graphs. Resolving a dependency graph into an ordered sequence is an instance of this problem. For 10 points, name this problem of flattening a directed acyclic graph into a list. ■END■
Buzzes
Player | Team | Opponent | Buzz Position | Value |
---|---|---|---|---|
Aseem Keyal | The Catastrophic Implosion of Packet Sub | BHSU | 88 | 10 |
Rahul Keyal | The anti-STOON-dahl cabal (the tall Keyal et al.) | Team Name Think Detail | 125 | 10 |
Raul Passement | Romanos IV Diogenes’ Macaroni Grill | Saint Peter Andre 3000 | 144 | 0 |
Shahar Schwartz | Saint Peter Andre 3000 | Romanos IV Diogenes’ Macaroni Grill | 144 | 0 |
Stephen Liu | Curse you, Periplus the Platypus! | The Plague (anime)" was redirected to: "Oran High School Host Club | 144 | 0 |