Transpose on vertex symmetric digraphs

2014/07/03 by Vance Faber, Faber, Vance
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Interconnection Networks and Systems #cs.DS #math.CO #msc:68M10

paper · pdf · doi:10.48550/arxiv.1407.0958

12 pages

arxiv created 2014/07/03 · arxiv updated 2014/07/04

Abstract

We discuss transpose (sometimes called universal exchange or all-to-all) on vertex symmetric networks. We provide a method to compare the efficiency of transpose schemes on two different networks with a cost function based on the number processors and wires needed to complete a given algorithm in a given time.

Related

• Global sum on symmetric networks
• Expansion of permutations as products of transpositions
• Global communication algorithms for Cayley graphs
• TRANS-Net: an Efficient Peer-to-Peer Overlay Network Based on a Full Transposition Graph
• Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry-Breaking Problems