Question
For a graph matching, this type of path alternates between unmatched and matched edges and is used in the blossom algorithm. For 10 points each:
[10h] Give this type of path. Each of these paths of a given number of edges is computed at once in Dinic’s algorithm.
ANSWER: augmenting path
[10e] In the paper that introduced the blossom algorithm, Jack Edmonds first described a class of problems solvable in this complexity class. It is an open question whether this class is equivalent or not to its nondeterministic analog.
ANSWER: P [or PTIME; or polynomial time]
[10m] Edmonds and Karp generalized a matching algorithm on bipartite graphs named for this country. Two mathematicians from this country name a model for generating random graphs in which nodes are initialized, and then edges are independently and randomly connected with equal probability.
ANSWER: Hungary [accept Hungarian algorithm] (The random graph generation model is the Erdős-Renyi model)
<Zhang, Other Science>
Summary
| 2024 ESPN @ Brown | 04/06/2024 | Y | 3 | 13.33 | 67% | 67% | 0% |
| 2024 ESPN @ Cambridge | 04/06/2024 | Y | 2 | 20.00 | 100% | 100% | 0% |
| 2024 ESPN @ Chicago | 03/23/2024 | Y | 6 | 15.00 | 100% | 33% | 17% |
| 2024 ESPN @ Columbia | 03/23/2024 | Y | 6 | 15.00 | 100% | 33% | 17% |
| 2024 ESPN @ Duke | 03/23/2024 | Y | 2 | 15.00 | 100% | 50% | 0% |
| 2024 ESPN @ Online | 06/01/2024 | Y | 3 | 16.67 | 100% | 67% | 0% |