Network Routing on Regular Directed Graphs from Spanning Factorizations

摘要: Networks with a high degree of symmetry are useful models for parallel processor networks. In earlier papers, we defined several global communication tasks (universal exchange, universal broadcast, summation) that can be critical when complex algorithms mapped to machines. We showed utilizing the make network optimization tractable problem. particular, Cayley graphs have desirable property certain routing schemes starting from single node transferred all nodes in way does not introduce conflicts. this paper, define concept spanning factorizations and show also used transfer other nodes. many (perhaps all) vertex transitive factorizations. Introduction. papers ([5], [8], [9]), which [9] (and [5]) extend transference idea class is more inclusive than graphs. Notation graph theory. This paper mainly focuses on directed derived groups. Here, G set vertices V collection E ordered pairs distinct ) , ( v u called edges. often let n number m If some pair appears once as an edge, then multigraph. Otherwise form elementary. The 2 tail edge head. Definition (Cayley coset graph). Let Γ finite group, Η subgroup ∆ subset. Suppose (i) ∅ = ∩ us generated by ∪ (ii) ∆Η ⊆ Η∆Η (iii) representatives . Then cosets } : { ∈ g δ When identity subgroup, graph. A graphG if any two there automorphism maps classic proof Sabidussi [13] shows only it An important aspect one construct using group required definition automorphisms fix generators correspond map neighbor.. Spanning 1-factor subgraph both in-degree out-degree equal 1. (Some authors 2factor. Our seems consistent notation undirected For example, edges bi-directional factor union 2-cycles, would ordinary graph.) It known every regular d has 1-factoring 1-factors. completeness, give here. Fact Every where disjoint decomposition into Proof. Form auxiliary B new u′ ′ each bipartite so Hall’s Marriage Theorem, decomposed Each these 1-factors corresponds order create scheme exchange (often transpose – see [10]) consider additional properties.