×

On bandwidth, cutwidth, and quotient graphs. (English) Zbl 0881.68089

Summary: The bandwidth and the cutwidth are fundamental parameters related to many problems modeled in terms of graphs. In this paper, we present a general method for finding upper bounds of the bandwidth of a graph from the ones the quotient graph and induced subgraphs issued from any of its partitions, as well as an equivalent result for cutwidth. Moreover, general lower bounds are obtained by using vertex- and edge-bisection notions.
These results are applied, in a second time, to several interconnection networks. By choosing convenient vertex partitions and judicious internal numberings of the vertices of the partition blocks, we prove in this paper original bounds for the binary de Bruijn and Butterfly graphs, and summarize results for the Shuffle-Exchange, FTT, and CCC graphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
68M10 Network design and communication in computer systems

Keywords:

bandwidth; cutwidth
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. D. BARTH, Réseaux d’interconnexion : Structures et Communications, Thèse de Doctorat, LaBRI, Université Bordeaux-I, 351 cours de la Libération, 33405 Talence, France, janvier 1994.
[2] 2. D. BARTH, F. PELLEGRINI, A. RASPAUD and J. ROMAN, On Bandwidth, Cutwidth, and Quotient graphs, Research report 814-94, LaBRI, Université Bordeaux-I, 351 cours de la Libération, 33405 Talence, France, mars 1994.
[3] 3. A. BEL HALA, Congestion optimale du plongement de l’hypercube H (n) dans la chaîne P (2n), Rairo Informatique Théorique et Applications, 1993, 27 (4), pp. 1-17. Zbl0803.68091 · Zbl 0803.68091
[4] 4. A. BEL HALA, Communications dans les réseaux d’interconnexion : plongements optimaux de l’hypercube. Thèse de Doctorat, LaBRI, Université Bordeaux-I, 351 cours de la Libération, 33405 Talence, France, janvier 1995.
[5] 5. C. BERGE, Graphs and Hypergraphs, North Holland Publishing, 1973. Zbl0254.05101 · Zbl 0254.05101
[6] 6. P. Z. CHINN, J. CHVÀTALOVÀ, A. K. DEWDNEY and N. E. GIBBS, The Bandwidth Problem for Graphs and Matrices, A survey, Journal of Graph Theory, 1982, 6, pp. 223-254. Zbl0494.05057 MR666794 · Zbl 0494.05057 · doi:10.1002/jgt.3190060302
[7] 7. F. R. K. CHUNG, The Theory and Applications of Graphs, chapter Some Problems and Results in Labelling of Graphs, pp. 255-263, John Wiley, 1981. Zbl0468.05065 MR634531 · Zbl 0468.05065
[8] 8. R. FELDMANN and W. UNGER, The Cube-Connected Cycles network is a subgraph of the Butterfly network, Parallel Processing Letters, 1992, 2 (1), pp. 13-19.
[9] 9. A. FELLER, Automatic layout of low-cost quick-turnaround random-logic customs LSI devices, In Proc. 13th Design Automation Conf., pp. 79-85, San Francisco, 1976.
[10] 10. M. R. GAREY and D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979. Zbl0411.68039 MR519066 · Zbl 0411.68039
[11] 11. F. GAVRIL, Some NP-complete problems on graphs, In Proc. 11th conference on information sciences and Systems, pp. 91-95, John Hopkins University, Baltimore.
[12] 12. N. E. GIBBS, W. G. POOLE and P. K. STOCKMEYER, A comparison of several bandwidth and profile reduction algorithms, ACM Trans. Math. Software, 1976, 2, pp. 322-330. Zbl0345.65014 · Zbl 0345.65014 · doi:10.1145/355705.355707
[13] 13. E. M. GURARI and I. H. SUDBOROUGH, Improved dynamic algorithms for bandwidth minimization and the mincut linear arrangement problem, Journal of Algorithms, 1984, 5, pp. 531-546. Zbl0556.68012 MR769981 · Zbl 0556.68012 · doi:10.1016/0196-6774(84)90006-3
[14] 14. L. H. HARPER, Optimal assignement of number of vertices, J. SIAM, 1964, 12, pp. 131-135. Zbl0222.94004 · Zbl 0222.94004 · doi:10.1137/0112012
[15] 15. L. H. HARPER, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1966, 1, pp. 385-393. Zbl0158.20802 MR200192 · Zbl 0158.20802 · doi:10.1016/S0021-9800(66)80059-5
[16] 16. R. KOCK, T. LEIGHTON, B. MAGGS, S. RAO and A. ROSENBERG, Work-preserving emulations of fixed-connection networks, In Proc. 21st Annual Symposium on Theory of Computing, pp. 227-240, ACM, 1989.
[17] 17. T. H. LAI and A. S. SPRAGUE, Placement of the processors of a hypercube, Technical report, 1988. · Zbl 1395.68016
[18] 18. F. T. LEIGHTON, Complexity issues in VLSI. Optimal layouts for the shuffle exchange graph and other networks, in Foundations of Computing Series, The MIT press, 1983.
[19] 19. F. T. LEIGHTON, Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes, Morgan Kaufman Publisher, 1992. Zbl0743.68007 MR1137272 · Zbl 0743.68007
[20] 20. B. MONIEN and H. SUDBOROUGH, Embedding one interconnection network in another, Computing Supplements, 1990, 7, pp. 257-282. Zbl0699.68017 MR1059934 · Zbl 0699.68017
[21] 21. K. NAKANO, W. CHEN, T. MASUZAWA, K. HAGIHARA and N. TOKURA, Cut width and bisection width of hypercube graph, IEICE Transactions, J73-A, (4), pp. 856-862, april 1990, In Japanese.
[22] 22. C. H. PAPADIMITRIOU, The NP-completeness of the bandwidth minimization problem, Computing, 1976, 16, pp. 263-270. Zbl0321.65019 MR411243 · Zbl 0321.65019 · doi:10.1007/BF02280884
[23] 23. F. PELLEGRINI, Bounds for the bandwidth of the d-ary de Bruijn graph, Parallel Processing Letters. Special Number on Interconnection Networks, 1993, 3 (4), pp. 431-443.
[24] 24. F. PELLEGRINI, Application de méthodes de partition à la résolution de problèmes de graphes issus du parallélisme, Thèse de Doctorat, LaBRI, Université Bordeaux-I, 351 cours de la Libération, 33405 Talence, France, janvier 1995.
[25] 25. G. PERSKY, D. DEUTSCH and D. SCHWEIKERT, LTX-A minicomputer-based system for automated LSI layout, J. Design Automation and Fault Tolerant Computing, 1977, 1, pp. 217-255.
[26] 26. F. PREPARATA and J. VUILLEMIN, The Cube-Connected Cycles: a versatile network for parallel computation, Communications of the ACM, May 1981, 24 (5), pp. 300-309. MR614176
[27] 27. F. SHAHROKHI and L. A. SZEKELY, An algebraic approach to the uniform concurrent multicommodity flow. Theory and applications, Technical Report CRPDC-91-4, University of North Texas, 1991.
[28] 28. W. F. SMITH and I. ARANY, Another algorithm for reducing bandwidth and profile of a sparse matrix, In Proc. AFIPS 1976 NCC, pp. 341-352, Montvale, New Jersey, 1976, AFIP Press.
[29] 29. S. TRIMBERG, Automating chip layout, IEEE Spectrum, pp. 38-45, 1982.
[30] 30. H. YOSHIZAWA, H. KAWANISHI and K. KANI, A heuristic procedure for ordering MOS arrays, In Proc. of Design Automation Conference, pp. 384-393, 1975.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.