Application of some graph invariants to the analysis of multiprocessor interconnection networks
DOI:
https://doi.org/10.2298/YJOR0802173CKeywords:
multiprocessor systems, interconnection topologies, spectra of graphs, maximum vertex degree, diameterAbstract
Let G be a graph with diameter D, maximum vertex degree Δ, the largest eigenvalue λ1 and m distinct eigenvalues. The products mΔ and (D+1) λ1 are called the tightness of G of the first and second type, respectively. In the recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. We study these and some other types of tightness and some related graph invariants and demonstrate their usefulness in the analysis of multiprocessor interconnection networks. Tightness values for graphs of some standard interconnection networks are determined. We also present some facts showing that the tightness of the second type is a relevant graph invariant. We prove that the number of connected graphs with a bounded tightness is finite.References
Biggs, N.L. (1993) Algebraic graph theory. Cambridge, itd: Cambridge University Press / CUP
Brouwer, A.E., Cohen, A.M., Neumaier, A. (1989) Distance-regular graphs. Berlin, itd: Springer Verlag
Byrd, G.T., Delagi, B.A. (1987) Considerations for multiprocessor topologies. u: Technical report, STAN-CS-87-1144, Department of Computer Science, Stanford University
Cvetković, D., Davidović, T. (2008) Small multiprocessor interconnection networks. Submitted for publication
Cvetković, D.M., Dimitrijević, V., Milosavljević, M.M. (1992) A survey of some non-standard traveling salesman problems. Yugoslav Journal of Operations Research, vol. 2, br. 2, str. 163-185
Cvetković, D.M., Gutman, I. (1977) Note on branching. Croatica Chemica Acta, 49, 115-121
Cvetković, D.M., Rowlinson, P. (1990) The largest eigenvalue of a graph: A survey. Linear and Multilinear Algebra, 28(1): 3
Cvetković, D.M., Doob, M., Sachs, H. (1995) Spectra of graphs: Theory and application. Heidelberg-Leipzig: Barth Verlag
Elsässer, R., Královič, R., Monien, B. (2003) Sparse topologies with small spectrum size. Theoretical Computer Science, 307(3): 549
Ferreira, A., Morvan, M. (1997) Models for parallel algorithm design: An introduction. u: Migdalas A., Pardalos P., Storøy S. [ur.] Parallel Computing in Optimization, Dordrecht, itd: Kluwer Academic Publishers, str. 1-26
Fowler, P.W., Caporossi, G., Hansen, P. (2001) Distance matrices, wiener indices, and related invariants of fullerenes. Journal of Physical Chemistry A, 105 (25), str. 6232-6242
Fowler, P.W., Manolopoulos, D.E. (1995) An atlas of fullerenes. Oxford, itd: Oxford University Press / OUP
Gutman, I. (1980) Characteristic and matching polynomials of some compound graphs. Publ. Inst. Math., Beograd, 27(41), 61-66
Leighton, F.T. (1992) Introduction to parallel algorithms and architectures arrays trees hypercubes. San Mateo: Morgan Kaufmann
Sarkar, V. (1989) Partitioning and scheduling parallel programs for multiprocessors. Cambridge, MA, itd: Massachusetts Institute of Technology Press
Sih, G.C., Lee, E.A. (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Transactions on Parallel and Distributed Systems, vol. 4, br. 2, str. 175-187
Simić, S.K., Tošić, D.V. (2005) The index of trees with specified maximum degree. Communications in Mathematical and in Computer Chemistry / MATCH, vol. 54, br. 2, str. 351-362
Sørevik, T. (1997) A programmer's view of parallel computers. u: Migdalas, A., Pardalos, P., Storøy, S. [ur.] Parallel Computing in Optimization, Dordrecht, itd: Kluwer Academic Publishers, str. 57-72
van Dam, E. (1996) Graphs with few eigenvalues: An interplay between combinatorics and algebra. Tilburg: Tilburg University - Center for Economic Research, PhD thesis
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
