# Cutwidth of iterated caterpillars

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

- Volume: 47, Issue: 2, page 181-193
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLin, Lan, and Lin, Yixun. "Cutwidth of iterated caterpillars." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.2 (2013): 181-193. <http://eudml.org/doc/273025>.

@article{Lin2013,

abstract = {The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.},

author = {Lin, Lan, Lin, Yixun},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {circuit layout design; graph labeling; cutwidth; caterpillar; iterated caterpillar},

language = {eng},

number = {2},

pages = {181-193},

publisher = {EDP-Sciences},

title = {Cutwidth of iterated caterpillars},

url = {http://eudml.org/doc/273025},

volume = {47},

year = {2013},

}

TY - JOUR

AU - Lin, Lan

AU - Lin, Yixun

TI - Cutwidth of iterated caterpillars

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2013

PB - EDP-Sciences

VL - 47

IS - 2

SP - 181

EP - 193

AB - The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.

LA - eng

KW - circuit layout design; graph labeling; cutwidth; caterpillar; iterated caterpillar

UR - http://eudml.org/doc/273025

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory. Springer-Verlag, Berlin (2008). Zbl1134.05001MR2368647
- [2] F.R.K. Chung, Labelings of graphs, edited by L.W. Beineke and R.J. Wilson. Selected Topics in Graph Theory3 (1988) 151–168. Zbl0656.05058MR1205400
- [3] F.R.K. Chung, On the cutwidth and topological bandwidth of a tree. SIAM J. Algbr. Discrete Methods6 (1985) 268–277. Zbl0565.05019MR778007
- [4] J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surveys34 (2002) 313–356.
- [5] J.A. Gallian, A survey: recent results, conjectures, and open problems in labeling graphs. J. Graph Theory13 (1989) 491–504. Zbl0681.05064MR1010582
- [6] 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
- [7] T. Lengauer, Upper and lower bounds for the min-cut linear arrangement of trees. SIAM J. Algbr. Discrete Methods3 (1982) 99–113. Zbl0489.68060MR644961
- [8] Y. Lin, X. Li and A. Yang, A degree sequence method for the cutwidth problem of graphs. Appl. Math. J. Chinese Univ. Ser. B 17(2) (2002) 125–134. Zbl1004.05052MR1904908
- [9] Y. Lin, The cutwidth of trees with diameter at most 4. Appl. Math. J. Chinese Univ. Ser. B 18(3) (2003) 361–368. Zbl1040.05025MR2004690
- [10] H. Liu and J. Yuan, The cutwidth problem for graphs. Appl. Math. J. Chinese Univ. Ser. A 10 (3) (1995) 339–348. Zbl0839.05082MR1361048
- [11] B. Monien, The bandwidth minimization problem for caterpipals with hair length 3 is NP-complete. SIAM J. Algbr. Discrete Methods7 (1986) 505–512. Zbl0624.68059MR857587
- [12] J. Rolin, O. Sykora and I. Vrt’o, Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. Lect. Notes Comput. Sci.1017 (1995) 252–264. MR1400027
- [13] M. M. Syslo and J. Zak, The bandwidth problem: critical subgraphs and the solution for caterpillars. Annal. Discrete Math.16 (1982) 281–286. Zbl0494.05058MR686313
- [14] I. Vrt'o, Cutwidth of the r-dimensional mesh of d-ary trees. RAIRO Theor. Inform. Appl.34 (2000) 515–519. Zbl0976.05059MR1844716
- [15] M. Yanakakis, A polynomial algorithm for the min-cut arrangement of trees. J. ACM32 (1985) 950–989. Zbl0633.68063

## NotesEmbed ?

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