Cutwidth of the de Bruijn graph

André Raspaud; Ondrej Sýkora; Imrich Vrt'o

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

  • Volume: 29, Issue: 6, page 509-514
  • ISSN: 0988-3754

How to cite

top

Raspaud, André, Sýkora, Ondrej, and Vrt'o, Imrich. "Cutwidth of the de Bruijn graph." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 29.6 (1995): 509-514. <http://eudml.org/doc/92521>.

@article{Raspaud1995,
author = {Raspaud, André, Sýkora, Ondrej, Vrt'o, Imrich},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {upper bound; cutwidth; de Bruijn graph},
language = {eng},
number = {6},
pages = {509-514},
publisher = {EDP-Sciences},
title = {Cutwidth of the de Bruijn graph},
url = {http://eudml.org/doc/92521},
volume = {29},
year = {1995},
}

TY - JOUR
AU - Raspaud, André
AU - Sýkora, Ondrej
AU - Vrt'o, Imrich
TI - Cutwidth of the de Bruijn graph
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1995
PB - EDP-Sciences
VL - 29
IS - 6
SP - 509
EP - 514
LA - eng
KW - upper bound; cutwidth; de Bruijn graph
UR - http://eudml.org/doc/92521
ER -

References

top
  1. 1. D. BARTH, F. PELLEGRINI, A. RASPAUD, and J. ROMAN, On bandwidth, cutwidth and quotient graphs, RAIRO Informatique, Théorique et Applications, to appear. Zbl0881.68089MR1377027
  2. 2. A. BEL HALA, Congestion optimale du plongement de l'ypercube H (n) dans la chaine P (2n), RAIRO Informatique, Théorique et Applications, 1993, 27, pp. 1-17. Zbl0803.68091MR1252607
  3. 3. G. BILARDI and F. PREPARATA, Area-time lower bound techniques with application to sorting, Algorithmica, 1986, 1, pp. 65-91. Zbl0622.68044MR833119
  4. 4. G. BREBNER, Relating routing graphs and two-dimensional grids, in: Proc. VLSI: Algorithms and Architectures, North Holland, 1985. Zbl0564.94019MR803728
  5. 5. D. KLEITMAN, F. T. LEIGHTON, M. LEPLEY and G. L. MILLER, New layouts for the shuffle-exchange graph, in: Proc. 13th Annual ACM Symposium on Theory of Computing, ACM Press, 1981, pp. 278-292. 
  6. 6. T. LENGAUER, Upper and lower bounds for the min-cut linear arrangements problem on trees, SIAM J. Algebraic and Discrete Methods, 1982, 3, pp. 99-113. Zbl0489.68060MR644961
  7. 7. A. D. LOPEZ and H. F. S. LAW, A dense gate matrix layout method for MOS VLSI, IEEE Trans. Electron. Devices, 1980, 27, pp. 1671-1675. 
  8. 8. K. NAKANO, Linear layout of generalized hypercubes, in: Proc. 19th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 790, Springer Verlag, Berlin, 1994, pp. 364-375. MR1286286
  9. 9. C. D. THOMPSON, Area-time complexity for VLSI, in: Proc. 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 81-88. MR564622
  10. 10. J. D. ULLMAN, Computational Aspects of VLSI, Computer Science Press, Rockville, 1984. Zbl0539.68021
  11. 11. M. YANNAKAKIS, A polynomial algorithm for the Min Cut Linear Arrangement of trees, J. ACM, 1985, 32, pp. 950-988. Zbl0633.68063MR810346

NotesEmbed ?

top

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.