A Random Graph Generator
Monica Van Horn · 2003
Random graph generation is commonly used in studying solutions to approximation algorithms. If random graphs can be generated, they provide a way to test algorithms for hard problems that have no optimal solution. By using these graphs, simulations can be used to determine, on the average, how well an algorithm performs. It is also possible to generate 'bad' graphs that will be able to approach some worst case solutions to algorithms. This paper will discuss the design and implementation of a random graph generator as well as its use on a scheduling problem for distributed/parallel systems. The design of our generator must take into consideration the number of nodes in the graph, the number of levels of the graph, the number of children for each node, and the height and width of each graph. Many truly random graphs turn out to look very similar to each other. That is why we also decided to generate graphs that were 'random' under certain constraints that would better test our algorithms. Lastly, we will discuss how the generator could be used to help others simulate their graph algorithm problems.