Some routing and sorting algorithms.

摘要

We consider, for d > 1, a directed d-dimensional hypercube, Q_d = (V,E), where V is a set of 2d nodes, each denoted by a distinct binary string of length d, and E is the set of edges (x, y), such that X, Y ∈ V differ in exactly one position of their bit strings. Given a permutation of the vertices of Q_d, which describes a source-destination mapping, we study the existence of a set of paths from each source to each destination such that no edge of Q_d is assigned to more than one path. For a multiprocessor connected in such a manner, such a set of paths could be used for circuit switching of messages between source-destination processors (nodes). We show that for any automorphism of Q_d, there is such a set of paths. The size of the automorphism class in Q_d is (d!) 2d. We also show that there is such a set of paths for all permutations of Q₄.; We prove that there is such a set of paths for a much bigger class of permutations. The size of this class is NN/2, where N = 2 d is the number of nodes in Q_d.; Sorting a permutation by reversals and transpositions is not only an interesting combinatorial problem, but also adequately models genome rearrangements. It can be used to analyze genomes evolution and mutation that is based on comparison of gene orders and the global rearrangements, i.e., inversions and transpositions of gene fragments. This sorting problem is conjectured to be NP-hard. We study the sorting of signed permutations, as the genes sequences occur in oriented blocks. We establish a lower bound for the number of steps to sort any given permutation. Based on the lower bound, we show two approximation algorithms. The first one is a 2-approximation algorithm. The time complexity is O(n2), where n is the length of the permutation to be sorted. The second one is a 5/3-approximation algorithm. The time complexity is O(n 3).