On bandwidth, cutwidth, and quotient graphs
Barth, Dominique ; Pellegrini, François ; Raspaud, André ; Roman, Jean
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 487-508 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1995__29_6_487_0,
     author = {Barth, Dominique and Pellegrini, Fran\c cois and Raspaud, Andr\'e and Roman, Jean},
     title = {On bandwidth, cutwidth, and quotient graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {29},
     year = {1995},
     pages = {487-508},
     mrnumber = {1377027},
     zbl = {0881.68089},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1995__29_6_487_0}
}

Barth, Dominique; Pellegrini, François; Raspaud, André; Roman, Jean. On bandwidth, cutwidth, and quotient graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) pp. 487-508. http://gdmltest.u-ga.fr/item/ITA_1995__29_6_487_0/

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. 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. 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. | Numdam | Zbl 0803.68091

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. C. Berge, Graphs and Hypergraphs, North Holland Publishing, 1973. | Zbl 0254.05101

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. | MR 666794 | Zbl 0494.05057

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. | MR 634531 | Zbl 0468.05065

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. 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. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, San Francisco, 1979. | MR 519066 | Zbl 0411.68039

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. 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. | Zbl 0345.65014

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. | MR 769981 | Zbl 0556.68012

14. L. H. Harper, Optimal assignement of number of vertices, J. SIAM, 1964, 12, pp. 131-135. | Zbl 0222.94004

15. L. H. Harper, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1966, 1, pp. 385-393. | MR 200192 | Zbl 0158.20802

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. T. H. Lai and A. S. Sprague, Placement of the processors of a hypercube, Technical report, 1988.

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. F. T. Leighton, Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes, Morgan Kaufman Publisher, 1992. | MR 1137272 | Zbl 0743.68007

20. B. Monien and H. Sudborough, Embedding one interconnection network in another, Computing Supplements, 1990, 7, pp. 257-282. | MR 1059934 | Zbl 0699.68017

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. C. H. Papadimitriou, The NP-completeness of the bandwidth minimization problem, Computing, 1976, 16, pp. 263-270. | MR 411243 | Zbl 0321.65019

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. 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. 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. 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. | MR 614176

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. 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. S. Trimberg, Automating chip layout, IEEE Spectrum, pp. 38-45, 1982.

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.