We will use GTgraph to generate small (N < 10e5) random graphs for correctness tests and some experimental tests. Currently, we are generating graphs using GTgraph-ssca2, an implementation of the SSCA2 graph generator. Can we generate adversarial graphs to demonstrate our algo's superiority?

• Verify cut samples are valid (i.e. the edges exist) the vast majority, if not all the time
• Verify correctness on small generated graphs
• Verify correctness on a massive generated graph to test handling of values near the numerical limit

• Determine the rate of invalid cut samples and the respective rates of type I and II errors
• Determine the RTE/WA rate on many small generated graphs
• Benchmark memory usage against a naive connected-components implementation on small generated graphs
• Benchmark against massive graphs with simulated insert/delete streams
• Find the largest size of graph we can process with this algo (that we can't with a naive algo)
• Benchmark against other external-memory MST implementations