no. 6
On bandwidth, cutwidth, and quotient graphs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 6, pp. 487-508 
@article{ITA_1995__29_6_487_0,
     author = {Barth, Dominique and Pellegrini, Fran\c{c}ois 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},
     pages = {487--508},
     year = {1995},
     publisher = {EDP Sciences},
     volume = {29},
     number = {6},
     mrnumber = {1377027},
     zbl = {0881.68089},
     language = {en},
     url = {https://www.numdam.org/item/ITA_1995__29_6_487_0/}
}
TY  - JOUR
AU  - Barth, Dominique
AU  - Pellegrini, François
AU  - Raspaud, André
AU  - Roman, Jean
TI  - On bandwidth, cutwidth, and quotient graphs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1995
SP  - 487
EP  - 508
VL  - 29
IS  - 6
PB  - EDP Sciences
UR  - https://www.numdam.org/item/ITA_1995__29_6_487_0/
LA  - en
ID  - ITA_1995__29_6_487_0
ER  - 
%0 Journal Article
%A Barth, Dominique
%A Pellegrini, François
%A Raspaud, André
%A Roman, Jean
%T On bandwidth, cutwidth, and quotient graphs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1995
%P 487-508
%V 29
%N 6
%I EDP Sciences
%U https://www.numdam.org/item/ITA_1995__29_6_487_0/
%G en
%F 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) no. 6, pp. 487-508. https://www.numdam.org/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. | Zbl | Numdam

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

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

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

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

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

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

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

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

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

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

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

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

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.