Cutwidth of the de Bruijn graph
Raspaud, André ; Sýkora, Ondrej ; Vrt'o, Imrich
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 509-514 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1995__29_6_509_0,
     author = {Raspaud, Andr\'e and S\'ykora, Ondrej and Vrt'o, Imrich},
     title = {Cutwidth of the de Bruijn graph},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {29},
     year = {1995},
     pages = {509-514},
     mrnumber = {1377028},
     zbl = {0880.05054},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1995__29_6_509_0}
}

Raspaud, André; Sýkora, Ondrej; Vrt'o, Imrich. Cutwidth of the de Bruijn graph. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) pp. 509-514. http://gdmltest.u-ga.fr/item/ITA_1995__29_6_509_0/

1. D. Barth, F. Pellegrini, A. Raspaud, and J. Roman, On bandwidth, cutwidth and quotient graphs, RAIRO Informatique, Théorique et Applications, to appear. | Numdam | MR 1377027 | Zbl 0881.68089

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

3. G. Bilardi and F. Preparata, Area-time lower bound techniques with application to sorting, Algorithmica, 1986, 1, pp. 65-91. | MR 833119 | Zbl 0622.68044

4. G. Brebner, Relating routing graphs and two-dimensional grids, in: Proc. VLSI: Algorithms and Architectures, North Holland, 1985. | MR 803728 | Zbl 0564.94019

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

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

9. C. D. Thompson, Area-time complexity for VLSI, in: Proc. 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 81-88. | MR 564622

10. J. D. Ullman, Computational Aspects of VLSI, Computer Science Press, Rockville, 1984. | Zbl 0539.68021

11. M. Yannakakis, A polynomial algorithm for the Min Cut Linear Arrangement of trees, J. ACM, 1985, 32, pp. 950-988. | MR 810346 | Zbl 0633.68063