Subscribe

Subscribe to our Newsletter and get informed about new publication regulary and special discounts for subscribers!

BMSA > Volume 20 > Network Routing on Regular Directed Graphs from...
< Back to Volume

Network Routing on Regular Directed Graphs from Spanning Factorizations

Full Text PDF

Abstract:

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, universal summation) that can be critical tasks when complex algorithms are mapped to parallel machines. We showed that utilizing the symmetry can make network optimization a tractable problem. In particular, we showed that Cayley graphs have the desirable property that certain routing schemes starting from a single node can be transferred to all nodes in a way that does not introduce conflicts. In this paper, we define the concept of spanning factorizations and show that this property can also be used to transfer routing schemes from a single node to all other nodes. We show that all Cayley graphs and many (perhaps all) vertex transitive graphs have spanning factorizations.

Info:

Periodical:
Bulletin of Mathematical Sciences and Applications (Volume 20)
Pages:
9-24
Citation:
R. Dougherty and V. Faber, "Network Routing on Regular Directed Graphs from Spanning Factorizations", Bulletin of Mathematical Sciences and Applications, Vol. 20, pp. 9-24, 2018
Online since:
November 2018
Export:
Distribution:
References:

[1] W.Y.C. Chen, V. Faber, E. Knill, Restricted routing and wide diameter of the cycle prefix network, in: D. Sotteau, D.F. Hsu, A. L. Rosenberg (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Interconnection Networks and Mapping and Scheduling Parallel Computations. 21 (1995).

DOI: https://doi.org/10.1090/dimacs/021/04

[2] W.Y.C. Chen, V. Faber, B. Li, Automorphisms of the cycle prefix digraph, 2014. Available: arXiv preprint arXiv:1404.4907.

[3] F. Comellas, M.A. Fiol, Vertex-symmetric digraphs with small diameter, Discrete Appl. Math. 58(1) (1995) 1-11.

DOI: https://doi.org/10.1016/0166-218x(93)e0145-o

[4] F. Comellas, M. Mitjana, Broadcasting in cycle prefix digraphs, Discrete Appl. Math. 83(1-3) (1998) 31-39.

DOI: https://doi.org/10.1016/s0166-218x(97)00102-9

[5] V. Faber, Global communication algorithms for hypercubes and other Cayley coset graphs, Technical Report, LA-UR 87-3136, Los Alamos National Laboratory, (1987).

[6] V. Faber, J. Moore, High-degree low-diameter interconnection networks with vertex symmetry: the directed case, Technical Report, LA-UR-88-1051, Los Alamos National Laboratory, (1988).

[7] V. Faber, J.W. Moore, W.Y.C. Chen, Cycle prefix digraphs for symmetric interconnection networks, Networks. 23(7) (1993) 641-649.

DOI: https://doi.org/10.1002/net.3230230707

[8] V. Faber, Global sum on symmetric networks, 2012. Available: arXiv preprint arXiv:1201.4153.

[9] V. Faber, Global communication algorithms for Cayley graphs, 2013. Available: arXiv preprint arXiv:1305.6349.

[10] V. Faber, Transpose on vertex symmetric digraphs, 2014. Available: arXiv preprint arXiv: 1407.0958.

[11] V. Faber, A. Streib, N. Streib, Ideal unit-time job shop scheduling, Unpublished preprint.

[12] B.D. McKay, M. Miller, J. Širáň, A note on large graphs of diameter two and given maximum degree, J. Combin. Theory Ser. B 74(1) (1998) 110-118.

DOI: https://doi.org/10.1006/jctb.1998.1828

[13] G. Sabidussi, Vertex transitive graphs, Monatsh. Math. 68(5) (1969) 426-438.

[14] M. Zdímalová, L. Stanekova, Which Faber-Moore-Chen digraphs are Cayley graphs?, Discrete Mathematics. 310(17-18) (2010) 2238-2240.

DOI: https://doi.org/10.1016/j.disc.2010.04.020
Show More Hide
Cited By:
This article has no citations.