On three fundamental graph enumeration problems and the corresponding graph generation algorithms

Green supercomputing has been attracting more and more attention due to the acknowledgement of environmental issues. This is especially the case in the field of supercomputing: given the large number of compute nodes involved, the power consumption of these machines is high, in the order of tens of megawatts. Efficient usage of supercomputers is thus key to minimise their power consumption, and one approach is to increase data transfer rates so that the computer can be returned into an energy efficient sleep mode rapidly. Parallel paths and especially disjoint paths routing is one solution to achieve such more efficient data transfers. Yet, the selection of mutually disjoint paths is complex, and in some cases graph enumeration can produce a solution whereas conventional approaches fail. The contribution of this paper is twofold: for the selected three fundamental graph enumeration problems, we give simple, easy to understand proofs that do not involve complex mathematical notions as in previous works; we describe and evaluate the corresponding graph generation algorithms and make comparisons to straightforward or conventional approaches. Not only theoretical evaluation but also empirical evaluation is conducted. Time complexity is shown to be optimal.