Search

A discussion of hypernet networks is presented, focusing on combinatorial properties. Topics include hypernet structure, node-disjoint paths, wide and fault diameters, transmission delay, and communication efficiency.

The design of shortest-path routing algorithms was found difficult for incomplete networks since most of them lack unified representation. An algorithm was proposed to route a message using a shortest-path for incomplete WK-recursive networks. This algorithm was found to take O(t) time for an intermediate mode to determine the next Node along the shortest path in O time preprocessing.

A parallel recognition algorithm is presented for efficiently recognizing a connected bipartite-permutation graph. Algorithm execution in O(log n) time on the Concurrent-Read Concurrent-Write Parallel Random Access Machine (PRAM) is possible if O(nsup3/log n) processors are used, or O(logsup2n) time on the Concurrent-Read Exclusive-Write PRAM using O(nsup3/logsup2n) processors are used. The algorithm is less computationally complex and has the ability to determine isomorphism of two bipartite-permutation graphs.

It has been possible to embed a Hamiltonian path between arbitrary two distinct vertices of an arrangement graph with edge faults. A Hamiltonian cycle arises if the two vertices are adjacent.

Research was conducted to examine faulty arrangement graphs and their Hamiltonicity. The difficulty of computing the probability of failures was avoided by specializing in the problem with ring being the guest network and the arrangement graph being the host network. Results indicate that the arrangement graph A(sub n1k) is more flexible than the star graph in adjusting the major design parameters, namely, the number of nodes, degree and diameter. The graph was also shown to be Hamiltonian despite its being faulty.