THE NOVA GRAPH: MORE DISJOINT PATHS WITH MINIMAL GRAPH AUGMENTATION

摘要

For the purpose of large scale computing, we are interested in linking computers into large interconnection networks. For such networks to be useful, the underlying graph must possess desirable properties such as a large number of vertices, high connectivity, and small diameter. In these graphs, we consider the "k-Disjoint Path Problem": given a graph G, and any k pairs of distinct nodes {(s_1,t_1), (s_2, t_2),…,(s_k, t_k)}, can there be found k-disjoint paths, each one connecting a pair?In this paper, we will demonstrate that a modification to the alternating group graph, whieh we have named the "Nova Graph," improves upon previous results regarding the k-Disjoint Path Problem. While maintaining the alternating group structure, which is useful in parallel-processing, the addition of a minimal number of edges increases the number of guaranteed disjoint paths. Furthermore, the Nova Graph gives the same number of disjoint paths as previously-observed graphs, while using far fewer vertices and edges.