On bandwidth, cutwidth, and quotient graphs

Dominique Barth; François Pellegrini; André Raspaud; Jean Roman

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1995)

  • Volume: 29, Issue: 6, page 487-508
  • ISSN: 0988-3754

How to cite


Barth, Dominique, et al. "On bandwidth, cutwidth, and quotient graphs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 29.6 (1995): 487-508. <http://eudml.org/doc/92520>.

author = {Barth, Dominique, Pellegrini, François, Raspaud, André, Roman, Jean},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {bandwidth; cutwidth},
language = {eng},
number = {6},
pages = {487-508},
publisher = {EDP-Sciences},
title = {On bandwidth, cutwidth, and quotient graphs},
url = {http://eudml.org/doc/92520},
volume = {29},
year = {1995},

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
PB - EDP-Sciences
VL - 29
IS - 6
SP - 487
EP - 508
LA - eng
KW - bandwidth; cutwidth
UR - http://eudml.org/doc/92520
ER -


  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. 

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.