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., Algebraic Graph Theory, (II edition), Cambridge University Press, Cambridge, 1993.
Brouwer, A.E., Cohen, A.M., and Neumaier, A., Distance-regular Graphs, Springer, Berlin, 1989.
Byrd, G.T., and Delagi, B.A., “Considerations for multiprocessor topologies”, Technical report, STAN-CS-87-1144, Department of Computer Science, Stanford University, 1987.
Cvetković, D., and Davidović, T., “Small multiprocessor interconnection networks”, Submitted for publication, 2008.
Cvetković, D., Dimitrijević, V., and Milosavljević, M., “A survey of some non-standard traveling salesman problems”, Yugoslav Journal of Operational Research, 2(2) (1992) 163-185.
Cvetković, D., and Gutman, I., “Note on branching”, Croat. Chem. Acta, 49 (1977) 115-121.
Cvetković, D., and Rowlinson, P., “The largest eigenvalue of a graph - a survey”, Linear and Multilinear Algebra, 28 (1990) 3-33.
Cvetković, D.M., Doob, M., and Sachs, H., Spectra of Graphs: Theory and Applications, (III edition), Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
Elsässer, R., Královič, R., and Monien, B., “Sparse topologies with small spectrum size”, Theor. Comput. Sci., 307 (2003) 549-565.
Ferreira, A., and Morvan, M., “Models for parallel algorithm design: An introduction”, in: A. Migdalas, P. Pardalos, S. Storøy (eds.), Parallel Computing in Optimization, Kluwer Academic Publishers, Dordrecht/Boston/London, 1997, 1-26.
Fowler, P.W., Caporossi, G., and Hansen, P., “Distance matrices, Wiener indices, and related invariants of fullerenes”, J. Chem. Phys. A, 105 (2001) 6232-6242.
Fowler, P.W., and Manolopoulos, D.E., An Atlas of Fullerenes, Clarendon Press, Oxford, 1995.
Gutman, I., “Characteristic and matching polynomials of some compaund graphs”, Publ. Inst. Math. (Beograd), 27(41) (1980) 61-66.
Leighton, F.T., Introduction to Parallel Algorithms and Architectures, Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.
Sarkar, V., Partitioning and Scheduling Parallel Programs for Multiprocessors, The M.I.T. Press, Cambridge, MA, 1989.
Sih, G.C., and Lee, E.A., “A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures”, IEEE Trans. Parallel and Distributed Systems, 4(2) (1993) 175-187.
Simić, S., and Tošić, D., “The index of trees with specified maximum degree”, MATCH Commun. Math. Comput. Chem., 54 (2005) 351-362.
Sørevik, T., “A programmer's view of parallel computers”, in: A. Migdalas, P. Pardalos, P. Storøy (eds.), Parallel Computing in Optimization, Kluwer Academic Publishers, Dordrecht/Boston/London, 1997, 57-72.
Van Dam, E., "Graphs with few eigenvalues: An interplay between combinatorics and algebra", PhD thesis, Center for Economic Research, Tilburg University, Tilburg, 1996.
Downloads
Published
Issue
Section
License
Copyright (c) 2008 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
