On bandwidth, cutwidth, and quotient graphs

 Access to full text

 Full (PDF)

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
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
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.05057MR666794
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.05065MR634531
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.68039MR519066
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
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.68012MR769981
14. 14. L. H. HARPER, Optimal assignement of number of vertices, J. SIAM, 1964, 12, pp. 131-135. Zbl0222.94004
15. 15. L. H. HARPER, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1966, 1, pp. 385-393. Zbl0158.20802MR200192
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. 
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.68007MR1137272
20. 20. B. MONIEN and H. SUDBOROUGH, Embedding one interconnection network in another, Computing Supplements, 1990, 7, pp. 257-282. Zbl0699.68017MR1059934
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.65019MR411243
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. 

1. André Raspaud, Ondrej Sýkora, Imrich Vrt'o, Cutwidth of the de Bruijn graph